Longest Palindromic Substring笔记

class Solution {
    
    /**
    *用的思路是 遍历每个元素，然后对每个元素进行两边扫描，扫描的同时可以判断是否回文串了，因为回文串必定是轴对称。
    
    *对每个元素两边扫描的时候要分两种情况：
        1.因为以一个元素为中心，可能构成奇数个字符的  回文串，也就是只关于那个元素对称；
        2.又或者是构成偶数个字符的  回文串，这个时候就不止关于那个元素对称，还有它旁边的元素，例如abccba，当遍历到c元素的时候，如果只是以它为中心，往两边扩散，会立刻发现b!=c，然后就判断不出是回文串了。
    因此遍历的时候要对每个字符都进行两次判断，时间复杂度为O(n^2)
    */
    public String longestPalindrome(String s) {
        
        if(s.length() == 1)return s; //因为  如果s长度为1，进不了下面那个for循环……
        
        int longestPalindromeLength = 0;
        
        String longestPalindromeStr = "";
        
        for(int i = 0; i < s.length() - 1; i++) {
            //遍历每个字符，以每个字符为中心  进行判断以这个  字符为中心的所有字符串中有没  回文字符串，并求出最大的那个
            int oddLongestLength = findLongestPalindrome(s, i);
            if(oddLongestLength > longestPalindromeLength) {
                longestPalindromeLength = oddLongestLength;
                longestPalindromeStr = s.substring(i - oddLongestLength/2, i + oddLongestLength/2 + 1);//注意这个subString后面那个index是不取的……
            }
            
            int evenLongestLength = findLongestPalindrome(s, i, i + 1);
            if(evenLongestLength > longestPalindromeLength) {
                longestPalindromeLength = evenLongestLength;
                longestPalindromeStr = s.substring(i + 1 - evenLongestLength/2, i + evenLongestLength/2 + 1);//注意这个subString后面那个index是不取的……
            }
        }
        
        return longestPalindromeStr;
    }
    
    
    /**
     * 以一个index为中心，找以它为中心的  所有  回文字符串  而且是  字符个数为奇数的回文字符串，因为偶数的话，中心应该是两个。
     * @param s 字符串
     * @param centerIndex 中心字符的index
     * @return 那个最长的  回文字符串的  长度
     */
    private int findLongestPalindrome(String s, int centerIndex) {
        int tempLongestLength = 0;//代表以这个centerIndex为中心的所有回文串中的  最大
        
        for(int i = centerIndex, j = centerIndex; i >= 0 && j <= s.length() - 1; i--, j++) {
            if(s.charAt(i) == s.charAt(j)) {
                //说明出现了  一个回文串了
                if( (j - i + 1) > tempLongestLength ) {
                    tempLongestLength = j - i + 1;
                }
            } else {
                //如果不相等，说明不对称  直接break了
                break;
            }
        }
        return tempLongestLength;
    }
    
    
    /**
     * 找以 这两个index为中心，个数为偶数的  所有  的回文字符串
     * @param s 字符串
     * @param leftCenterIndex 左边中心
     * @param rightCenterIndex 右边中心
     * @return 这两个中心拓展的最长 的  回文字符串的长度
     */
    private int findLongestPalindrome(String s, int leftCenterIndex, int rightCenterIndex) {
        int tempLongestLength = 0;//代表以这个centerIndex为中心的所有回文串中的  最大
        
        for(int i =leftCenterIndex, j = rightCenterIndex; i >= 0 && j <= s.length() -1; i--, j++) {
            if(s.charAt(i) == s.charAt(j)) {
                 //说明出现了  一个回文串了
                if( (j - i + 1) > tempLongestLength ) {
                    tempLongestLength = j - i + 1;
                }
            } else {
                //如果不相等，说明不对称  直接break了
                break;
            }
        }
        return tempLongestLength;
        
    }
}

public String longestPalindrome(String s) {
        if (s == null)
            return null;
     
        if(s.length() <=1)
            return s;
     
        int maxLen = 0;
        String longestStr = null;
     
        int length = s.length();
     
        int[][] table = new int[length][length];
     
        //every single letter is palindrome
        for (int i = 0; i < length; i++) {
            table[i][i] = 1;
            longestStr = s.charAt(i) + ""; //此时  最大的  回文串就是  单个字咯
            maxLen = 1;//最大回文串长度就为1咯
        }
        
    
        //two consecutive same letters are palindrome
        for (int i = 0; i <= length - 2; i++) {
           
            if (s.charAt(i) == s.charAt(i + 1)){//相隔的两个字相等
                table[i][i + 1] = 1;
                longestStr = s.substring(i, i + 2);
                maxLen = 2;//两个相等的字符串嘛
            }    
        }
       
        //condition for calculate whole table
        //前面对于单个字也就是二维数组中对角线上的情况还有   间隔相等的情况  也就是j - i = 1的情况都处理了
        //这里是  对其他需要  借助动态规划也就是之前数组的结果来操作的情况  也就是  j - 1 >=2的情况
        for (int len = 3; len <= length; len++) {
            /*第一层循环   是以长度为基准的，因为这里处理的是j - i >=2的情况嘛，也就是比如abc，a和c这样的情况，也就是子串长度3以上的情况，所以第一层循环就描述这个，从3开始慢慢加
　　　　　　　　*直到table[0][length - 1]填好就可以有结果了
　　　　　　　 */
            
            
            for (int i = 0; i < length - len + 1; i++) {
                //这个条件是  因为len = j - 1 + 1，然后又有j < length得来的
                
                int j = len + i - 1;//len = j - 1 + 1
                
                if(s.charAt(i) == s.charAt(j) && table[i + 1][j - 1] == 1) {
                    table[i][j] = 1;
                    if(len > maxLen) {
                        longestStr = s.substring(i, j + 1);
                    }
                } else {
                    table[i][j] = 0;
                }
                
            }
        }
     
        return longestStr;
    }