5. Longest Palindromic Substring (最长回文子序列)

LeetCode 第5题

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

我的解题思路：

1、一个回文串有两种形式，奇数的回文串如(aba,abcba)。偶数的回文串如(aa,abba)。

2、时间复杂度为O(n)的解决方法。遍历字符串的每一个字符。以每一个字符为中心往外寻找。找到以这一个字符为中心的最大的回文串。遍历完所有的字符就可以找到最大的回文字符串了。

举例。以字符串 abacaba 作为输入来检索一下结果。奇数回文串

字符中心	i ，j，k	回文串	最大回文串
a	0,0,0	a	a
b	1,0,2	aba	aba
a	2,2,2	a	aba
c	3,0,6	abacaba	abacaba
a	4,4,4	a	abacaba
b	5,4,6	aba	abacaba
a	6,6,6	a	abacaba

再求一次偶数回文串，将偶数回文串和奇数回文串的比较找出最大的就是最大的回文子串了。

奇数我就不做举例了。

下面是Accept代码 

class Solution {
    public String longestPalindrome(String s) {
        int n = s.length();
        String ans = s.length()==1?s:"";
        for(int i=0;i<n;i++){
            int j=i;
            int k=i;
            while(j>=0&&k<=n-1&&s.charAt(j)==s.charAt(k)){   
                ans = ans.length()<(k-j+1)?s.substring(j,k+1):ans;
                j--;
                k++;
              
            }
           
        }
        for(int i=0;i<n;i++){
            int j=i;
            int k=i+1;
            while(j>=0&&k<=n-1&&s.charAt(j)==s.charAt(k)){
                ans = ans.length()<(k-j+1)?s.substring(j,k+1):ans;
                j--;
                k++;
                
            }
             
        }
        
        return ans;
        
    }
}