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

/**
 * 2种解题思路  1. 动态规划 2. 开花 3. 爆破
 */
public class _5 {
    static class Solution_1 {
        public String longestPalindrome(String s) {
            // dp[i][j] =  s.charAt(i) == s.charAt(j) && dp[i-1][j-1]
            //1. j - i < 3,那么只需要判断 s.charAt(i) == s.charAt(j)
            //时间复杂度 O(N * N )
            int l = 0;
            int r = 0;
            boolean[][] dp = new boolean[s.length()][s.length()];
            for (int j = 0; j < s.length(); j++) {
                for (int i = 0; i <= j; i++) {
                    dp[i][j] = s.charAt(i) == s.charAt(j) && (j -i < 3 || dp[i+1][j-1]);
                    if(dp[i][j] && j -i > r - l){
                        l = i;
                        r = j;
                    }
                }
            }
            return s.substring(l,r+1);
        }

    }
    static class Solution_2{
        //开花，比动态规划快，由于中心开花失败如果一直失败时间复杂度为O(N),
        //最坏情况下，所有字符重复，时间复杂度O(N*N)
        public String longestPalindrome(String s) {
            char[] chs = s.toCharArray();
            int l = 0;
            int r = 0;
            int left = 0;
            int right = 0;
            String res = "";
            for(int mid = 0;mid <= chs.length;mid++){
                int[][] candidates = {
                        {mid,mid+1},
                        {mid,mid}
                };
                for(int[] c : candidates){
                    l = c[0];
                    r = c[1];
                    while(r < chs.length&&l >= 0&& chs[l] == chs[r]){
                        if(right-left < r-l){
                            left = l;
                            right = r;
                        }
                        l--;
                        r++;
                    }
                }

            }
            return String.valueOf(chs,left,right-left+1);
        }
    }
    static class Solution_3{
        //爆破，时间复杂度 O(N*N*N)，随手写的未验证正确性
        public String longestPalindrome(String s) {
            int l = 0;
            int r = 0;
            for(int i = 0;i < s.length();i++){
                for(int j = 0;j < s.length();j++){
                    if(test(s,i,j) && j- i > r -l){
                        l = i;
                        r = j;
                    }
                }
            }
            return s.substring(l,r+1);
        }

        public boolean test(String s,int i,int j){
            while (i <= j ){
                if(s.charAt(i++) != s.charAt(j--)) return false;
            }
            return true;
        }
    }

}