# 0005. Longest Palindromic Substring
###### tags: `Leetcode` `Medium` `Dynamic Programming` `FaceBook` `Palindrome`
Link: https://leetcode.com/problems/longest-palindromic-substring/

## 思路
### 思路一 $O(N)$ $O(1)$
**中心扩散法**
和[0647. Palindromic Substrings](https://hackmd.io/VzhQ_CCOQlCtDDsY8dEY8Q)思路一样
由于所有的结果其实都是由 **一个char 或 两个连续相同的char**，左右各补上一个相同的char所产生的，所以就用expandAroundCenter函数来看 **一个char 或 两个连续相同的char** 是否有机会扩充，也就是他们左右两边的char是不是一样的，这个函数回传的值就是 以 **一个char 或 两个连续相同的char** 为中心的最长的回文串的长度

### 思路二 $O(N)$ $O(N)$
**动态规划**
建一个str.length()乘str.length()的boolean表格flag，因为i必须要小于j，(i是左端点，j是右端点)再加上已知的只有```flag[i][i] = true```，所以表格其实要以对角线为起点向右下扩充，因此，第一个回圈是在逐步增加 所要验证是否为回文串 的 字串的长度，第二个回圈则是在调整 left side 的位置。如果```flag[i] == flag[j]```, 两个char相等，那么```flag[i][j] = true```。或是如果```flag[i] == flag[j]```, 那么```flag[i][j] = flag[i+1][j-1]```。

**官方解答版：**
边界条件
## Java Code
### 思路一

class Solution {
    int maxLen;
    int left;
    int right;
    public String longestPalindrome(String s) {
        maxLen = 0;
        left = 0;
        right = 0;
        if(s.length()==0) return "";
        for(int i = 0;i < s.length();i++){
            expandAroundCenter(s, i, i+1);
            expandAroundCenter(s, i, i);
        }
        return s.substring(left, right+1);
    }
    private void expandAroundCenter(String s, int l, int r){
        int len = 0;
        while(l>=0 && r<s.length()){
            if(s.charAt(l)==s.charAt(r)){
                len+=l==r?1:2;
                l--;
                r++;
            }
            else{
                break;
            }
        }
        if(len > maxLen){
            maxLen = len;
            left = l+1;
            right = r-1;
        }
    }
}

### 思路二

class Solution {
    public String longestPalindrome(String str) {
        int str_len = str.length();
        int max_len = 1;
        int ans_begin = 0;

        if(str.length() == 1){
            return str;
        }
        boolean [][] flag = new boolean[str_len][str_len];

        for(int i = 0;i < str_len;i++){
            flag[i][i] = true;
        }

        char[] charArray = str.toCharArray();
        for(int len = 2; len <= str_len; len++){
            for(int i = 0; i < str_len; i++){
                int j = len+i-1;
                if(j>=str_len){
                    break;
                }
                if(charArray[i] == charArray[j]){
                    if(len == 2){
                        flag[i][j] = true;
                    }
                    else{
                        flag[i][j] = flag[i+1][j-1];
                    }
                }
                if(flag[i][j] && len>max_len){
                    max_len = len;
                    ans_begin = i;
                }
            }
        }
        return str.substring(ans_begin, ans_begin+max_len);
    }
}

## 踩过的坑们
如果max_len的值没有给成1，那么遇到测资"ac"的时候就会什么都不会输出，但应该输出"a"或"c"
for(int len = 2; len <= str_len; len++)一开始没有加=，但实际答案的长度有可能和字串长度相等