Palindrome Partitioning | Leetcode

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: Recursively process the string, cutting off an initial portion of it and recursing on the rest of the string. When we reach an empty string, add the result only if the current list of strings is not empty.

The algorithm is very similar to that of getting all possible combinations of substrings within the string except that the characters within all substrings must appear in the same sequence as the characters in the original string. We add one more check, isPalindrome(), to each substring, to see if any particular combination should be accepted or not.

public class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> answer = new ArrayList<>();
        process(answer, new ArrayList<String>(), s);
        return answer;
    }
    
    private void process(List<List<String>> answer, List<String> list, String s) {
        if (s.length() == 0) {
            if (!list.isEmpty()) {
                answer.add(new ArrayList<String>(list));
            }
            return;
        }
        for (int i = 1; i <= s.length(); i++) {
            String t = s.substring(0, i);
            if (!isPalindrome(t)) continue;
            list.add(t);
            process(answer, list, s.substring(i));
            list.remove(list.size() - 1);
        }
    }
    
    private boolean isPalindrome(String s) {
        if (s.length() == 1) return true;
        for (int i = 0, j = s.length() - 1; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) return false;
        }
        return true;
    }
}