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.

For example, given s = "aab",
Return

[
  ["aa","b"],
  ["a","a","b"]
]

Solution:

This problem is similar to Subset.

We try all possible cut the string at index i, and check if there is a palindrome start from this position.

If so, we put this palindrome to the list, and increase i next to the end of this palindrome, and recursively try this method.

If we find we reach the end of the string, we know all the cut are valid and put the cut list into the result.



Code:

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new ArrayList<>();
        if (s == null || s.length() == 0) {
            return result;
        }
        helper(s, result, new ArrayList<String>(), 0);
        return result;
    }
    
    public void helper(String s, List<List<String>> result, List<String> list, int start) {
        if (start == s.length()) {
            result.add(new ArrayList<>(list));
            return;
        }
        
        for (int i = start; i < s.length(); i++) {
            String sub = s.substring(start, i + 1);
            if (!isPalindrome(sub)) {
                continue;
            }
            list.add(sub);
            helper(s, result, list, i + 1);
            list.remove(list.size() - 1);
        }
    }
    
    public boolean isPalindrome(String s) {
        int i = 0;
        int j = s.length() - 1;
        while (i < j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }
        return true;
    }
}