---
tags: LeetCode,Top 100 Liked Questions
---
# 5. Longest Palindromic Substring
https://leetcode.com/problems/longest-palindromic-substring/
## 題目敘述
Given a string s, return the longest palindromic substring in s.
## Example
Example 1:

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

Example 2:

Input: s = "cbbd"
Output: "bb"

Example 3:

Input: s = "a"
Output: "a"

Example 4:

Input: s = "ac"
Output: "a"

## 解題想法
### 1.Z algorithm
因Palindrome為左右對稱的string，故以每個char以及char中的空白為中心(若"abba"對稱"bb"中的空白)，左右相同就擴張

class Solution {
public:
string longestPalindrome(string s)
{
    int n = s.length();
    int best = 1;  //length of longest palindromic substring
    int start = 0; //begin of longest palindromic substring 

    for (int i = 0; i < n; i++) // odd length palindrome
    {
        int len = 1; //signle char is a palindrome
        int l = i - 1;
        int r = i + 1;
        while (l >= 0 && r < n && s[l] == s[r])
        {
            l--;
            r++;
            len += 2;
        }
        if (len > best)
        {
            best = len;
            start = l + 1;
        }
    }
    for (int i = 0; i < n; i++) // even length palindrome
    {
        int len = 0; 
        int l = i - 1;
        int r = i;
        while (l >= 0 && r < n && s[l] == s[r])
        {
            l--;
            r++;
            len += 2;
        }
        if (len > best)
        {
            best = len;
            start = l + 1;
        }
    }
    return s.substr(start, best);
   }
};

時間複雜度為O(N^2)

### 2.Bottom-up DP
參考[https://leetcode.com/problems/longest-palindromic-substring/discuss/151144/Bottom-up-DP-Logical-Thinking](https://https://leetcode.com/problems/longest-palindromic-substring/discuss/151144/Bottom-up-DP-Logical-Thinking)

DP需要三個部分

State Variable:state(s,e) //代表str[s,e]是Palindrome 從s開始e結束

Goal State:max(e-s+1) () //得到最長Palindrome

Extract Transition from Base Case Transitions:

for s = e, "a" is palindromic,
for s + 1 = e, "aa" is palindromic (if str[s] = str[e])
for s + 2 = e, "aba" is palindromic (if str[s] = str[e] and "b" is palindromic)
for s + 3 = e, "abba" is palindromic (if str[s] = str[e] and "bb" is palindromic)

於是可以推得

for s + n = e,str[s,e] is palindromic (if str[s] = str[e] and str[s+1,e-1] is palindromic)

class Solution {
public:
string longestPalindrome(string s)
{
    int n = s.length();
    vector<vector<bool>> dp(n,vector<bool>(n,false));
    // state[i][j] true if s[i, j] is palindrome.

    for (int i = 0; i < n; i++)
    {
        dp[i][i] = true; //base case(signle char is a palindrome)
    }

    int longestPalindrome_start = 0, longestPalindrome_len = 1;

    for (int start = n - 1; start >= 0; start--)
    {
        for (int end = start + 1; end < n; end++)
        {
            if (s[start] == s[end] && (dp[start + 1][end - 1] || (end-start)==1))
            //end-start==1 is signle char 
            {
                dp[start][end] = true;
                if (end - start + 1 > longestPalindrome_len)
                {
                    longestPalindrome_len = end - start + 1;
                    longestPalindrome_start = start;
                }
            }
        }
    }
    return s.substr(longestPalindrome_start, longestPalindrome_len);
   }
};

時間複雜度為O(N^2)