DEV Community

Cover image for 131. Palindrome Partitioning
Harsh Rajpal
Harsh Rajpal

Posted on

131. Palindrome Partitioning

Problem Statement:

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s.

Example 1:

Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]

Example 2:

Input: s = "a"
Output: [["a"]]

Constraints:

  • 1 <= s.length <= 16
  • s contains only lowercase English letters.

Solution:

Algorithm:

  1. Use DFS to traverse all the possible partitions.
  2. Use a helper function to check if the current substring is a palindrome.
  3. If the current substring is a palindrome, add it to the path and continue to traverse the rest of the string.
  4. If the current substring is not a palindrome, do not add it to the path and continue to traverse the rest of the string.
  5. If the current index is equal to the length of the string, add the current path to the result.
  6. After the traversal is completed, return the result.

Code:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs(s, 0, path, res);
        return res;

    }

    private void dfs(String s, int index, List<String> path, List<List<String>> res) {
        if (index == s.length()) {
            res.add(new ArrayList<>(path));
            return;
        }
        for (int i = index; i < s.length(); i++) {
            if (isPalindrome(s, index, i)) {
                path.add(s.substring(index, i + 1));
                dfs(s, i + 1, path, res);
                path.remove(path.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String s, int left, int right) {
        while (left < right) {
            if (s.charAt(left) != s.charAt(right)) {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }

}

Enter fullscreen mode Exit fullscreen mode

Time Complexity:
O(n*2^n)O(n∗2n) The time complexity of the backtracking algorithm is exponential, because in the worst case, we need to add n-1 separators into a string of length n, which results in 2^n2

Space Complexity:
O(n)O(n) The space complexity of the backtracking algorithm is linear, because in the worst case, the depth of the recursion tree can reach nn.

Image of Datadog

Create and maintain end-to-end frontend tests

Learn best practices on creating frontend tests, testing on-premise apps, integrating tests into your CI/CD pipeline, and using Datadog’s testing tunnel.

Download The Guide

Top comments (0)

Hostinger image

Get n8n VPS hosting 3x cheaper than a cloud solution

Get fast, easy, secure n8n VPS hosting from $4.99/mo at Hostinger. Automate any workflow using a pre-installed n8n application and no-code customization.

Start now

👋 Kindness is contagious

Please leave a ❤️ or a friendly comment on this post if you found it helpful!

Okay