[leetcode] Longest Palindromic Substring

https://leetcode.com/problems/longest-palindromic-substring/

找出最长的palindrom substring

做法就是每个index 都作为中心点，以0,和length-1为边界把偶数和奇数长的substring找出来
然后记录下最长的

public class Solution {
    public String longestPalindrome(String s) {
        if (s.length() == 0){
            return "";
        }
        
        String longestEver = s.substring(0,1);
        for (int i = 0; i <= s.length()-2; i++){
            String temp = findPadlindrome(i,i,s);
            String temp2 = findPadlindrome(i,i+1,s);
            String longer = temp.length()>temp2.length()?temp:temp2;
            longestEver = longer.length()>longestEver.length()?longer:longestEver;
        }
        return longestEver;
    }
    
    private String findPadlindrome(int centerLeft, int centerRight, String s){
        if (s.charAt(centerLeft) != s.charAt(centerRight)){
            return "";
        }
        int begin = centerLeft;
        int end = centerRight;
        while (begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
            begin -= 1;
            end += 1;
        }
        
        return s.substring(begin+1, end);
    }
}

Google了一下， DP的算法
就是用 check[a][b] 代表 substring a到b 是不是palindrom
可以分解成
check[a][b] = check[a+1][b-1] str[a] == str[b]
当a == b时 check[a][b] = true

public class Solution {
    public String longestPalindrome(String s) {
        boolean check[][] = new boolean[s.length()][s.length()];
        int longest = 0;
        int start=0, end=0;
        for (int i = 0; i < s.length(); i++){
            check[i][i] = true;
            for (int j = 0; j < i; j++){
                check[j][i] = s.charAt(i) == s.charAt(j) && ((i-j < 2) ||check[j+1][i-1]);
                if (check[j][i] && longest < (i-j+1)){
                    longest = i-j+1;
                    start = j;
                    end = i;
                }
            }
        }
        return s.substring(start, end+1);
    }
}