## 题目 给定一个字符串 s, 找到 s 中最长的回文子串你可以假设 s 长度最长为 1000
示例:
输入: "babad"
输出: "bab"
注意: "aba" 也是有效答案
示例:
输入: "cbbd"
输出: "bb"
思路
一开始是想用最笨的方法来解的, 也就是找出所有的字串, 然后再对所有的子串进行回文检测, 并记录长度这种方式时间复杂度可想而知, O(n)*O(n)*O(n)=O(n^3) 所以这种肯定是不能满足我们要求的
ok, 那我们来分析一下这个问题, 先把这个问题特殊化;
假如输入的字符串长度就是 1
那么这个字符串的最长回文串就是它自己, 长度就是 1
假如字符串长度为 2, 它要是回文串的化, 就需要两个字符是相等的
即: s[i] == s[j] 且 i-j=1(此处假定 i 是较大索引位置)
那么对于 i-j>1 的情况下呢? 是不是只要满足下面的条件就可以了:
即: s[i] == s[j]&&s[i-1] == s[j+1]
其实这种思路就是动态规划关于动态规划的理论性文字就不码了, 有兴趣的小伙伴阔以自行学习下面就针对这个问题码一下代码:
- public String longestPalindrome(String s) {
- // 长度为 1, 返回当前串
- if (s.length()==1){
- return s;
- }
- // 长度为 2 并且两个字符相等则返回
- if (s.length()==2&&s.charAt(0)==s.charAt(1)){
- return s;
- }
- // 用于标记 isLongestPalindrome[j][i] 即从 j 到 i 是否是回文串;
- // 如 isLongestPalindrome[1][5]==true 则表示字符串索引位置从 1 到 5 的子串是回文串
- boolean[][] isLongestPalindrome = new boolean[s.length()][s.length()];
- // 最长回文串初始最大为 0
- int maxlen = 0;
- // 对应的 maxlen 的开始索引位置
- int beginIndex = 0;
- // 对应的 maxlen 的结束索引位置
- int lastIndex = 0;
- for (int i=0;i<s.length();i++){
- int j=i;
- while(j>=0){
- // 满足上述的第三个条件, 即当前 s.charAt(i)==s.charAt(j) 并
- // 且 s[j+1 到 i-1] 也是回文串
- if (s.charAt(i)==s.charAt(j)&&(i-j<2||isLongestPalindrome[j+1][i-1])){
- isLongestPalindrome[j][i]=true;
- if (maxlen < i-j+1) {
- beginIndex = j;
- lastIndex = i+1;
- maxlen = i-j+1;
- }
- }
- j--;
- }
- }
- return s.substring(beginIndex,lastIndex);
- }
来源: https://juejin.im/post/5aa51c49f265da23870e748d