题解 | #最长回文子串#
最长回文子串
http://www.nowcoder.com/practice/b4525d1d84934cf280439aeecc36f4af
1、动态规划
- 定义二维数组dp[length][length]，如果dp[left][right]为true，则表示字符串从left到right是回文子串，如果dp[left][right]为false，则表示字符串从left到right不是回文子串
- 递推公式
- 如果dp[left+1][right-1]为true，我们判断s.charAt(left)和s.charAt(right)是否相等，
- 如果相等，那么dp[left][right]肯定也是回文子串，否则dp[left][right]一定不是回文子串。
dp[left][right]=s.charAt(left)==s.charAt(right)&&dp[left+1][right-1]
- 初始化
- 如果s.charAt(left)!=s.charAt(right)，那么字符串从left到right是不可能构成子串的，直接跳过即可。
- 如果s.charAt(left)==s.charAt(right)，字符串从left到right能不能构成回文子串还需要进一步判断：
- 如果left==right，也就是说只有一个字符，我们认为他是回文子串。即dp[left][right]=true（left==right）
- 如果right-left<=2，类似于"aa"，或者"aba"，我们认为他是回文子串。即dp[left][right]=true（right-left<=2）
- 如果right-left>2，我们只需要判断dp[left+1][right-1]是否是回文子串，才能确定dp[left][right]是否为true还是false。即dp[left][right]=dp[left+1][right-1]
| index | a | b | b | b | a |
|---|---|---|---|---|---|
| 1 | left | right | |||
| 2 | left1 | left2 | right |
2、中心点扩散
遍历字符串的每一个字符，然后以当前字符为中心往两边扩散，查找最长的回文子串
