“给定一个字符串,将字符串分割成一些子串,使每个子串都是回文串,返回所有可能的分割方案。”
题目链接:
来源:力扣(LeetCode)
链接: 131. 分割回文串 - 力扣(LeetCode) (leetcode-cn.com)
给你一个字符串 s
,请你将 s
分割成一些子串,使每个子串都是 回文串 。返回 s
所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1:
输入: s = "aab"
输出: [["a","a","b"],["aa","b"]]
示例 2:
输入: s = "a"
输出: [["a"]]
题意要求找出字符串所有的分割方案,可以考虑使用回溯的方法遍历所有可能性进行判断。
递归树的模型是一颗二叉树,每一个节点表示剩余没有扫描到的字符串,产生分支是截取了剩余字符串的前缀:
然后从根节点到子节点的路径,就是结果集中的一个结果,使用深度优先遍历算法,记录所有可能的结果。
代码参考:
class Solution {
boolean[][] f;
List<List<String>> ret = new ArrayList<List<String>>();
List<String> ans = new ArrayList<String>();
int n;
public List<List<String>> partition(String s) {
n = s.length();
f = new boolean[n][n];
for (int i = 0; i < n; ++i) {
Arrays.fill(f[i], true);
}
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
f[i][j] = (s.charAt(i) == s.charAt(j)) && f[i + 1][j - 1];
}
}
dfs(s, 0);
return ret;
}
public void dfs(String s, int i) {
if (i == n) {
ret.add(new ArrayList<String>(ans));
return;
}
for (int j = i; j < n; ++j) {
if (f[i][j]) {
ans.add(s.substring(i, j + 1));
dfs(s, j + 1);
ans.remove(ans.size() - 1);
}
}
}
}
时间复杂度:O(n · 2n)
其中n是字符串的长度。
空间复杂度:O(n2)
其中n是字符串的长度。
在判断s[i,j]是否为回文串时,使用了两个指针分别指向i和j,每次判断两个指针指向的字符是否相同,直到两个指针相遇。