Question

link

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

Stats

Ratings/Color = 1(white) 2(lime) 3(yellow) 4/5(red)

Analysis

This is an extremely classic question.

It’s not very hard to solve, although it looked impossible at first.

Solution

The solution is DFS.

It’s very standard DFS code, I will not go into coding details. This type of “return all possible path” question is always related to DFS, keep this in mind!

The code is borrowing ideas from peking2’s blog. He also had an analysis on this series of questions:

我觉得一般有三种变形，解法各有不同。

1. 最后结果是一个整数，比如Palindrome Partitioning II。这个用DP来解
2. 最后求一个结果，比如最小切法。这个用DP＋backtrack来解
3. 求所有的结果。这个一般用DFS来解。

This question is the 3rd case. Fish Lei also said the same.

这种需要输出所有结果的基本上都是DFS的解法

Code

public ArrayList<ArrayList<String>> partition(String s) {
    // int len = s.length();
    ArrayList<ArrayList<String>> ans = new ArrayList<ArrayList<String>>();
    helper(ans, new ArrayList<String>(), s, 0);
    return ans;
}

private void helper(ArrayList<ArrayList<String>> ans, ArrayList<String> cur, 
        String s, int start) {
    int len = s.length();
    if (start == len) {
        ans.add(new ArrayList<String>(cur));
        return;
    }
    for (int i = start + 1; i <= len; i ++) {
        String sub = s.substring(start, i);
        if (isPal(sub)) {
            cur.add(sub);
            helper(ans, cur, s, i);
            cur.remove(cur.size() - 1);
        }
    }
}

private boolean isPal(String str) {
    int left = 0, right = str.length() - 1;
    while (left < right) {
        if (str.charAt(left) != str.charAt(right)) 
            return false;
        left++;
        right--;
    }
    return true;
}