一、题目
1、算法题目
“给定一个字符串，将字符串分割成一些子串，使每个子串都是回文串，返回所有可能的分割方案。”
题目链接：
来源：力扣（LeetCode）
链接： 131. 分割回文串 - 力扣（LeetCode） (leetcode-cn.com)
2、题目描述
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
回文串 是正着读和反着读都一样的字符串。
示例 1： 输入： s = "aab" 输出： [["a","a","b"],["aa","b"]] 复制代码
示例 2： 输入： s = "a" 输出： [["a"]] 复制代码
二、解题
1、思路分析
题意要求找出字符串所有的分割方案，可以考虑使用回溯的方法遍历所有可能性进行判断。
递归树的模型是一颗二叉树，每一个节点表示剩余没有扫描到的字符串，产生分支是截取了剩余字符串的前缀：
- 如果前缀字符串是回文，则可以产生分支和节点
- 如果前缀字符串不是回文，则不产生分支和节点
然后从根节点到子节点的路径，就是结果集中的一个结果，使用深度优先遍历算法，记录所有可能的结果。
2、代码实现
代码参考：
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); } } } } 复制代码
网络异常，图片无法展示
|
3、时间复杂度
时间复杂度：O(n · 2n)
其中n是字符串的长度。
空间复杂度：O(n2)
其中n是字符串的长度。
三、总结
在判断s[i,j]是否为回文串时，使用了两个指针分别指向i和j，每次判断两个指针指向的字符是否相同，直到两个指针相遇。
