这道题是 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)]
}
个人笔记

每个分治法都改写为动态规划法。这里解法三正是解法二的动态规划写法。看起来可能不一样,把解法三理解为解法二的字符串“反过来”就可以了。解法三种找的回文串 s[j,i] 就是解法二中的“回文前缀”。

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

上述的每个解法中,我们使用 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]))
		}
	}
}

结语

本文发表在我的博客 https://imageslr.com/。我也会分享更多的题解,一起交流,共同进步!

附录

copy:

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