【力扣】【131】【中等】分割回文串
作者：shizhishi |
发布时间： |
分类：算法精解 |
声明：个人技术博客 • 非官方 • 仅供技术学习交流
这道题难点分为两部分：找出 **回文串** 和**分割字符串**，这里用 **动态规划** 解决第一个问题，使用 **回溯** 解决第二个问题 * 首先我们要明白为什么要在这里使用动态规划 假如我们使用循环去找回文串，那么会有重复的判断，比如**abccba**，从第一位开始，**abccba**是回文串，这种判断是基...
这道题难点分为两部分：找出 **回文串** 和**分割字符串**，这里用 **动态规划** 解决第一个问题，使用 **回溯** 解决第二个问题
### 使用动态规划解决找出回文串
* 首先我们要明白为什么要在这里使用动态规划
假如我们使用循环去找回文串，那么会有重复的判断，比如**abccba**，从第一位开始，**abccba**是回文串，这种判断是基于**bccb**和**cc**是回文串，但是当遍历到**b**和**c**时，又会判断**bccb**和**cc**是否是回文串。
所以使用动态规划能避免重复判断。
* 那么针对这道题，我们如何进行分解
* 每个字符都是回文串，比如： a , b 。
* 如果两个字符相同，并且中间的字符串是回文串，那么这条字符串一定是回文串，比如： aba , abba
既然如此，我们就能从**b ==> aba**，再到其他回文串判断
总结为：只要两个字符间的字符串是回文串，并且两个字符相同，那么就为回文串
### 整理为表格
| | a | a | b |
| --- | --- | --- | --- |
| a | ○ | ○ | × |
| a | | ○ | × |
| b | | | ○ |
a的本身是回文串
首尾字符a和b不相同，即使中间的字符是回文串，aab也不是回文串
### 使用回溯分割字符串
分割字符串时有将单个字符作为一个回文串和将字符串当做一个回文串，因此在回溯后，需要恢复回溯前的状态
### 代码实现
```
class Solution {
boolean[][] f;
List> ret = new ArrayList>();
List ans = new ArrayList();
int n;
public List> partition(String s) {
n = s.length();
f = new boolean[n][n];
//初始化
for (int i = 0; i = 0; --i) {
for (int j = i + 1; j (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);
}
}
}
}
```