131. Palindrome Partitioning

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

A palindrome string is a string that reads the same backward as forward.

1
2
3
4
5
6
7
8
9
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

 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
class Solution {
    
    public List<List<String>> partition(String s) {
        List<List<String>> res = new ArrayList<>();
        List<String> current = new ArrayList<>();
        back(0, s.toCharArray(), current, res);
        return res;
    }

    void back(int index, 
              char[] s, List<String> current, 
              List<List<String>> res) {
        
        if (index == s.length) {
            res.add(new ArrayList<>(current));
            return;
        }
        
        for (int i = index + 1; i <= s.length; i++) {
            if (isPalindrom(s, index, i)) {
                current.add(new String(Arrays.copyOfRange(s, index, i)));
                back(i, s, current, res);
                current.remove(current.size() - 1);
            }
        }
    }
    
    boolean isPalindrom(char[] s, int i, int j) {
        if (i == j) return false;
        if (j - i == 1) return true;
        while (i < j) {
            if (s[i++] != s[--j]) {
                return false;
            }
        }
        return true;
    }
}

Solution#

Solution