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.

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

Solution: DFS, Subsets变种题 考虑每个间隙是partition还是不partition

public List<List<String>> partition(String s) {
    List<List<String>> result = new ArrayList<>();
    partitionHelper(s, new ArrayList<String>(), result);
    return result;
}

public void partitionHelper(String s, ArrayList<String> curr, List<List<String>> result) {
    if (s.length() == 0) {
        result.add(new ArrayList<String>(curr));
        return;
    }
    for (int i = 0; i < s.length(); i++) {
        String currString = s.substring(0, i + 1);
        if (isPalindrome(currString)) {
            curr.add(currString);
            partitionHelper(s.substring(i + 1), curr, result);
            curr.remove(curr.size() - 1); //important
        }
    }
}

public boolean isPalindrome(String s) {
    int start = 0;
    int end = s.length() - 1;
    while (start <= end) {
        if (s.charAt(start) != s.charAt(end)) {
            return false;
        }
        start++;
        end--;
    }
    return true;
}

Share