【LeetCode】131 分割字符串

这道题是 LeetCode 131 题。

给定一个字符串 s，将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。

示例:

输入: "aab"
输出:
[
  ["aa","b"],
  ["a","a","b"]
]

解法一：回溯法

使用递归实现，在每一层中，使用一个 for 循环判断每个长度的前缀是否是回文串。如果是，将其添加到结果中，进入下一层。直到字符串为空串，这时候得到一个新的结果。

时间复杂度：$O(n×n^n)$。递归树的节点数为 $O(n^n)$，判断每个子串是否是回文串需要 $O(n)$。
空间复杂度：$O(n)$，递归的最大深度。

代码：

var res [][]string

func partition(s string) [][]string {
	if len(s) == 0 {
		return nil
	}
	res = nil
	dfs(s, nil)
	return res
}

func dfs(s string, cur []string) {
	if s == "" {
		tmp := copy(cur)
		res = append(res, tmp)
		return
	}
	for i := 1; i <= len(s); i++ {
		if isPalindrome(s[:i]) {
			dfs(s[i:], append(cur, s[:i]))
		}
	}
}

func isPalindrome(s string) bool {
	l, r := 0, len(s)-1
	for l <= r && s[l] == s[r] {
		l++
		r--
	}
	return l > r
}

解法二：分治法

将大问题分解为若干个小问题，这些小问题的解合起来就是大问题的解。

对这道题而言，如果某个前缀是回文串，那么先求除了该前缀的子串的解集，然后每个解里加上这个这个前缀，求得到当前字符串的部分解。遍历全部的前缀，汇总解集。

这道题和解法一的思路很类似。解法一是在叶节点的时候新增一个解，解法二是在左右子树返回的时候得到中间解，最后返回到根节点时得到全部解。

时间复杂度：$O(n×n^n)$。递归树的节点数为 $O(n^n)$，判断每个子串是否是回文串需要 $O(n)$。
空间复杂度：$O(n)$，递归的最大深度。

代码：

func partition(s string) [][]string {
	if len(s) == 0 {
		return [][]string{[]string{}}
	}
	var res [][]string
	for i := 1; i <= len(s); i++ {
		if isPalindrome(s[:i]) {
			for _, v := range partition(s[i:]) {
				tmp := copy(v)
				tmp = append([]string{s[:i]}, tmp...) // 要插入在开头
				res = append(res, tmp)
			}
		}
	}
	return res
}

解法三：动态规划

和解法二思路一样，每个字符串的解集，可以由其子串的解集得到。解法二是将大问题分解为小问题，递归求解，最后再汇总。而动态规划的思路，则是将这个过程反过来，先求得所有小问题的解，然后依次得到大问题的解。这是一种树形 DP，采用由叶至根的后根遍历，即子节点将有用信息向上传递给父节点，逐层上推。

时间复杂度：$O(n×n^n)$。同解法二，但实际上是比解法二要更小的。因为解法二在递归过程中，会有重复计算的节点，而动态规划则对这些节点做了缓存，不需要再重复计算。比如 aabb，在解法二中会有这样的计算过程：

aabb
 -> a | abb
   -> a | a | bb 这里计算了一次 bb
 -> aa | bb 这里又计算了一次 bb

空间复杂度：$O(n)$。状态数组的长度为 n，不包含保存结果所需的空间。

代码：

vector<vector<string>> partition(string s) {
    int n = s.length();
    vector<vector<bool>> flag(n, vector<bool>(n));
    for (int l = 1; l <= n; l++) {
        for (int i = 0; i + l <= n; i++) {
            int j = i + l - 1;
            if (s[i] == s[j]) flag[i][j] = i+1 > j-1 || flag[i+1][j-1];
            else flag[i][j] = false;
        }
    }
    vector<vector<vector<string>>> dp(n+1); // dp[i+1] 表示以 s[i] 结尾的子串的全部解
    dp[0].push_back(vector<string>()); // 必须手动初始化 dp[0] 为包含一个空集，表示空串的情况
    for (int i = 0; i < n; i++) { // 依次更新 dp[i+1]
        for (int j = 0; j <= i; j++) { // 遍历 s[0~i] 的所有后缀 s[j~i]
            if (flag[j][i]) {
                for (auto arr : dp[j]) { // dp[j] 表示 s[0~j-1] 的所有解
                    auto newarr = vector<string>(arr);
                    newarr.push_back(s.substr(j, i-j+1));
                    dp[i+1].push_back(newarr); // dp[i+1] -> s[0~i]
                }
            }
        }
    }
    return dp[n];
}

func partition(s string) [][]string {
	if len(s) == 0 {
		return nil
	}
	dp := make([][][]string, len(s)+1) // dp[i+1] 表示以 s[i] 结尾的子串的全部解
	dp[0] = [][]string{[]string{}}     // 手动初始化 dp[0] 为空集，表示空串的情况
	for i := 0; i < len(s); i++ {      // 遍历每个字符 s[i]
		for j := 0; j <= i; j++ { // 遍历以 s[i] 结尾的所有子串
			if isPalindrome(s[j : i+1]) { // 如果子串 s[j,i] 是回文串
				for _, v := range dp[j] { // 那么以 s[j-1] 结尾的子串的每个解加上 s[j,i]，都是 dp[i] 的一个新的解
					tmp := copy(v)
					dp[i+1] = append(dp[i+1], append(tmp, s[j:i+1]))
				}
			}
		}
	}
	return dp[len(s)]
}

优化判断回文串的时间复杂度

上述的每个解法中，我们使用 isPalindrome 函数判断某个子串是否是回文串。一共 $O(n^2)$ 个子串，判断每个子串需要从头到尾遍历该子串，$O(n)$，总体时间复杂度就是 $O(n^3)$。

但实际上，在判断某个子串 s[i~j] 是否是回文串时，如果我们已经知道 s[i+1~j-1] 是回文串，那么只需要再判断 s[i]==s[j] 即可，这样就可以在 $O(1)$ 的时间内判断某个子串是否是回文串。

我们可以用动态规划的方法，把每个子串是否是回文串保存起来：

• dp[i][j] 表示 s[i~j] 是否是回文串
• dp[i][j] = s[i] == s[j] && dp[i+1][j-1]
• 先判断所有长度为 1 的子串，再判断所有长度为 2 的，长度为 3 的…以此类推

先提前将这个数组计算出来，然后算法过程中就能直接得到某个子串是否是回文串。

这部分时间复杂度从 $O(n^3)$ 降为 $O(n^2)$。

以解法一为例，代码变为：

var res [][]string

func partition(s string) [][]string {
	if len(s) == 0 {
		return nil
	}
	res = nil
	dp := make([][]bool, len(s))
	for i, _ := range dp {
		dp[i] = make([]bool, len(s))
	}
	for l := 1; l <= len(s); l++ {
		for i := 0; i <= len(s)-l; i++ {
			j := i + l - 1
			dp[i][j] = s[i] == s[j] && (i+1 > j-1 || dp[i+1][j-1])
		}
	}
	dfs(dp, 0, s, nil)
	return res
}

func dfs(dp [][]bool, start int, s string, cur []string) {
	if start >= len(s) {
		tmp := copy(cur)
		res = append(res, tmp)
		return
	}
	for i := start; i < len(s); i++ {
		if dp[start][i] {
			dfs(dp, i+1, s, append(cur, s[start:i+1]))
		}
	}
}

附录

copy：

func copy (nums []string) []string {
    res := make([]string ,len(nums))
    for i, v := range nums {
        res[i] = v
    }
    return res
}