131. Palindrome Partitioning

发表于 | 分类于 | 阅读次数

Description

  1. 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”]
    ]
  2. Given a string s, partition s such that every substring of the partition is a palindrome.
    Return the minimum cuts needed for a palindrome partitioning of s.
    For example, given s = “aab”,
    Return 1 since the palindrome partitioning [“aa”,”b”] could be produced using 1 cut.

题解1

这道题的意思是对于给定的字符串有多少种分法使得分完后的每个子串都是回文串。看到这道题，第一感觉就是先用dfs分割，然后对分割后的串判断是否为回文串，果然，参考了leetcode上的discuss给出的几种高票答案，票数最高的就是该方法，不过其他答案我觉得写的非常好，不从时间复杂度和空间复杂度来看，仅从解决问题的方式来说

Java: Backtracking solution

参考：https://discuss.leetcode.com/topic/6186/java-backtracking-solution
该解法配有详细的说明，比如对于字符串”aab”，从a分割，这样a和子串ab；从aa分割，这样会得到aa和子串b；从aab分割，这样会得到aab；而子串可以继续重复上述过程，在分割的过程中判断分割后左边的字符串是否满足回文，如果不满足就不用继续往下分割了，如下图所示：
http://i58.tinypic.com/2la69p2.png
代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public List<List<String>> partition(String s) {
   List<List<String>> res = new ArrayList<List<String>>();
   List<String> list = new ArrayList<String>();
   dfs(s,0,list,res);
   return res;
}
public void dfs(String s, int pos, List<String> list, List<List<String>> res){
    if(pos==s.length()) res.add(new ArrayList<String>(list));
    else{
        for(int i=pos;i<s.length();i++){
            if(isPal(s,pos,i)){
                list.add(s.substring(pos,i+1));
                dfs(s,i+1,list,res);
                list.remove(list.size()-1);
            }
        }
    }
}
public boolean isPal(String s, int low, int high){
    while(low<high) if(s.charAt(low++)!=s.charAt(high--)) return false;
    return true;
}

讲一下这个代码的执行过程，以字符串”aabcbd”为例：
list=[“a”]
list=[“a”,”a”]
list=[“a”,”a”,”b”]
list=[“a”,”a”,”b”,”c”]
list=[“a”,”a”,”b”,”c”,”b”]
list=[“a”,”a”,”b”,”c”,”b”,”d”]，到底，添加到res中
list=[“a”,”a”,”b”,”c”,”b”]，回退
list=[“a”,”a”,”b”,”c”]，bd不满足，回退
list=[“a”,”a”,”b”]，cb不满足，cbd不满足，回退
list=[“a”,”a”]，bc不满足，bcb满足
list=[“a”,”a”,”bcb”,”d”] 添加到res中
list=[“a”,”a”]，bcbd不满足，回退
list=[“a”]，ab不满足，abc不满足，abcb不满足，abcbd不满足，回退
list=[“aa”]，重复上面的过程，后面有省略过程
list=[“aa”,”b”,”c”,”b”,”d”]添加到res中
list=[“aa”]，bc不满足，bcb满足
list=[“aa”,”bcb”,”d”]添加到res中
“aab”不满足，”aabc”不满足，”aabcb”不满足，”aabcbd”不满足，返回
这个里面有个问题，就是比较子串是否是回文串，会重复比较，所以说思路比较简单，但是不是最优解

My Java DP only solution without recursion. O(n^2)

参考：https://discuss.leetcode.com/topic/2884/my-java-dp-only-solution-without-recursion-o-n-2
这个方法就比较好了，非递归+DP，最重要的是使用二维数组来记录子串是否为回文串，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
	public static List<List<String>> partition(String s) {
	int len = s.length();
	List<List<String>>[] result = new List[len + 1];
	result[0] = new ArrayList<List<String>>();
	result[0].add(new ArrayList<String>());
	boolean[][] pair = new boolean[len][len];
	for (int i = 0; i < s.length(); i++) {
		result[i + 1] = new ArrayList<List<String>>();
		for (int left = 0; left <= i; left++) {
			if (s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])) {
				pair[left][i] = true;
				String str = s.substring(left, i + 1);
				for (List<String> r : result[left]) {
					List<String> ri = new ArrayList<String>(r);
					ri.add(str);
					result[i + 1].add(ri);
				}
			}
		}
	}
	return result[len];
}

这个代码中的pair[i][j]表示的是字符串s中第i个字符到第j个字符组成的字符串是否为回文串，比如这句话

1
s.charAt(left) == s.charAt(i) && (i-left <= 1 || pair[left + 1][i - 1])

表示的是表示的是从第left个字符和第i个字符相等后，要么它们之间的差距小于等于1，要么在它们中间的串是回文串，则它们就是回文串
这个代码原理其实和上面的差不多，这里以s=”aabcbd”为例，先分析s=”a”的情况，然后再分析s=”aa”的情况，继续分析s=”aab”,s=”aabc”,s=”aabcb”,s=”aabcbd”，对当前的每一次分析都会牵扯到前面的结果，下面是该程序运行过程中result的变化：
result[0]:[[]]
result[1]:[[a]]
result[2]:[[aa],[a,a]]
result[3]:[[aa,b],[a,a,b]]
result[4]:[[aa,b,c],[a,a,b,c]]
result[5]:[[aa,bcb],[a,a,bcb],[aa,b,c,b],[a,a,b,c,b]]
result[6]:[[aa,bcb,d],[a,a,bcb,d],[aa,b,c,b,d],[a,a,b,c,b,d]]
这个过程时间复杂度有讨论中提到为O(2^n)，因为如果s=”aaaaaaaa…”,对result[i]分析可以知道result[i]中元素的个数是前面所有的和，即最坏时间复杂度为O(2^n)

Java DP + DFS solution

参考:https://discuss.leetcode.com/topic/37756/java-dp-dfs-solution
这个将第一种方法中判断是否为回文的函数用dp解决了，这个方法是第一种的优化，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
public List<List<String>> partition(String s) {
    List<List<String>> res = new ArrayList<>();
    boolean[][] dp = new boolean[s.length()][s.length()];
    for(int i = 0; i < s.length(); i++) {
        for(int j = 0; j <= i; j++) {
            if(s.charAt(i) == s.charAt(j) && (i - j <= 2 || dp[j+1][i-1])) {
                dp[j][i] = true;
            }
        }
    }
    helper(res, new ArrayList<>(), dp, s, 0);
    return res;
}
private void helper(List<List<String>> res, List<String> path, boolean[][] dp, String s, int pos) {
    if(pos == s.length()) {
        res.add(new ArrayList<>(path));
        return;
    }
    
    for(int i = pos; i < s.length(); i++) {
        if(dp[pos][i]) {
            path.add(s.substring(pos,i+1));
            helper(res, path, dp, s, i+1);
            path.remove(path.size()-1);
        }
    }
}

1-liner Python, Ruby

参考：https://discuss.leetcode.com/topic/19370/1-liner-python-ruby
最后给一个有趣的方法，很简短，给出这样代码的原因：Depends on how obvious I find it and on my current mood。 O(∩_∩)O哈哈~

1
2
3
4
5
def partition(self, s):
    return [[s[:i]] + rest
            for i in xrange(1, len(s)+1)
            if s[:i] == s[i-1::-1]
            for rest in self.partition(s[i:])] or [[]]

discuss中给出了比较好理解的代码：

1
2
3
4
5
6
7
8
9
def partition(self, s):
    ret = []
    for i in range(1, len(s)+1):
        if s[:i] == s[i-1::-1]:
            for rest in self.partition(s[i:]):
                ret.append([s[:i]]+rest)
    if not ret:
        return [[]]
    return ret

实质上还是第一种方法，只不过是反着来得，实际执行过程如下，同样以s=”aabcbd”为例：
一开始返回[[]],然后生成[[d]]，到bd，变为[[b,d]]，到cbd变为[[c,b,d]],到bcbd中因为bcb为回文串，需要判断partition(d)，变成[[b,c,b,d],[bcb,d]]，然后回退到abcbd,[[a,b,c,b,d],[a,bcb,d]]，回退到aabcbd，此时由于aa是回文串，需要调用partition(bcbd)，注意这个是重复的，如果要优化该代码，应该从此处入手（不过这样的话，就和第二种方法差不多了）；最后变为[[a,a,b,c,b,d],[a,a,bcb,d],[aa,b,c,b,d],[aa,bcb,d]]

题解2

这道题我先给出我的一个简单的好理解的解法，虽然超时了(26/29)，但是还是有意义的，就是先生成一个dp的回文表，表示第i个字符到第j个字符是否是回文串，然后在使用dfs分割所有可能的情况，取其中最小的，这里是有重复的，需要使用dp解决，我是想不到了，就看看discuss吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public static int minCut(String s) {
    int end=s.length();
    boolean [][]dp=new boolean[end][end];
    int[]maxCount=new int[1];
    maxCount[0]=Integer.MAX_VALUE;
    for(int i=0;i<end;i++){
        for(int j=0;j<=i;j++){
            if(i==j)dp[j][i]=true;
            else dp[j][i]=(s.charAt(i)==s.charAt(j))&&((i-j<=1)||dp[j+1][i-1]);
        }
    }
    dfs(dp,0,end,0,maxCount);
    return maxCount[0];
}
private static void dfs(boolean[][] dp, int i,int end, int count,int[]maxCount) {
    if(count>maxCount[0])return;
    if(i==end||dp[i][end-1]){
        if(count<maxCount[0])maxCount[0]=count;
    };
    for(int j=end-1;j>=i;j--){
        if(dp[i][j]){
            dfs(dp,j+1,end,count+1,maxCount);
        }
    }
}

如下是leetcode上给出的一种很经典的解法(双dp)，也就是相当于我的dfs给用for来写，外层循环来对i增加，对于0-i之间的字符串，判断最小的分割数，其中dp判断最小分割数的cut并不是只与前一个有关，而是前面的全部，比如字符串aaaabcbaa的情况，会从第3个a前分开，而不是b前分开。
见：https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36
This can be solved by two points:
cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.
If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].
The 2nd point reminds us of using dp (caching).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int minCut(String s) {
    char[] c = s.toCharArray();
    int n = c.length;
    int[] cut = new int[n];
    boolean[][] pal = new boolean[n][n];
    
    for(int i = 0; i < n; i++) {
        int min = i;
        for(int j = 0; j <= i; j++) {
            if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                pal[j][i] = true;  
                min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
            }
        }
        cut[i] = min;
    }
    return cut[n - 1];
}

如果觉得有帮助，给我打赏吧！