Question

link

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"]
  ]

Stats

Frequency 4
Difficulty 3
Adjusted Difficulty 4
Time to use --------

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;
}