Problem

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

Definition

Palindrome Definition

Examples

Example 1:

1
2

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

Example 2:

1
2

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

Solution

Method 1 - Depth-first Search and Backtracking

In the examples, we can see each char itself is palindrome. For aab, we have a, a and b. But then we have to break aab again to aa and b. This is how the decision tree looks:

We have already seen how to Check if given string is palindrome or not.

Here is the video explanation:

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

class Solution {
    public List < List<String>> partition(String s) {
        List < List<String>> ans = new ArrayList<>();

        if (s == null || s.length() == 0) {
            return ans;
        }

        //track each possible partition
        dfs(s, 0, new ArrayList<String>(), ans);

        return ans;
    }


    private void dfs(String s, int idx, List<String> subAns, List < List<String>> ans) {
        //stop condition
        if (idx == s.length()) {
            ans.add(new ArrayList<String> (subAns));
            return;
        }

        for (int i = idx; i < s.length(); i++) {
            String str = s.substring(idx, i + 1);

            if (isPalindrome(str)) {
                subAns.add(str); // take the substr and store it in subAns & call the next substr from idx + 1
                dfs(s, i + 1, subAns, ans);
                subAns.remove(subAns.size() - 1); // remove the string, and try now with substr(idx, i + 2) for eg.
            }
        }
    }


    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        while (left < right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> ans = new ArrayList<>();

        if (s == null || s.length() == 0) {
            return ans;
        }

        dfs(s, 0, new ArrayList<String>(), ans, new HashMap<>());

        return ans;
    }

    private void dfs(String s, int idx, List<String> subAns, List<List<String>> ans, Map<String, Boolean> map) {
        //stop condition
        if (idx == s.length()) {
            ans.add(new ArrayList<String>(subAns));
            return;
        }

        for (int i = idx; i < s.length(); i++) {
            String str = s.substring(idx, i + 1);
            if (isPalindrome(str, map)) {
                subAns.add(str);
                dfs(s, i + 1, subAns, ans, map);
                subAns.remove(subAns.size() - 1);
            }
        }
    }

    private boolean isPalindrome(String str, Map<String, Boolean> map) {
        if (map.containsKey(str)) {
            return map.get(str);
        }
        boolean isPal = isPalindrome(str);
        map.put(str, isPal);
        return isPal;
    }

    private boolean isPalindrome(String str) {
        int left = 0;
        int right = str.length() - 1;

        while (left<right) {
            if (str.charAt(left) != str.charAt(right)) {
                return false;
            }

            left++;
            right--;
        }

        return true;
    }
}

Complexity

  • ⏰ Time complexity: O(n.2^n)
  • 🧺 Space complexity: O(n) (using recursion stack)