###### tags: `Leetcode` `medium` `dynamic programming` `python` `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 1:**

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

**Example 2:**

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

## 解題想法:
* 經典DP
* **dp[i][j]: s[i]~s[j]是否為迴文**
* **由後往前遍歷**
* 第一個loop:
* 讓i從倒數第二個開始
* for i in range(len(s)-2,-1,-1)
* 第二個loop
* 讓j跟在i後面
* for j in range(i+1,len(s))

## python (Sol1: DP):

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if len(s)<=1:
            return s
        #init
        dp=[[False]*len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i]=True #自己一定是true
        res=s[0]
        #dp 從尾開始 
        #dp[i][j] s[i]~s[j]是否為回文
        for i in range(len(s)-2,-1,-1):
            for j in range(i+1,len(s)):
                if s[i]==s[j]:
                    #若是隔壁or 各往內縮一格=true
                    if (j-i==1 or dp[i+1][j-1]==True):
                        dp[i][j]=True
                        if len(res)< j-i+1:
                            res=s[i:j+1]
        return res

if __name__ == '__main__':
    result = Solution()
    s = "afccfb"
    ans = result.longestPalindrome(s)
    print(ans)

## python (Sol2: Recursive):
* 額外寫個子函式判斷回文處理
* 主程式考量回文屬於奇數or偶數狀況

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s:
            return ""
        ans = ""
        for index in range(len(s)):
            #優化 若剩餘字數量<ans//2 則可以停止ㄌ
            if len(s)-index<len(ans)//2:
                break
            #case: aba
            cur_find = self.find_max_palindorme(s,index,index)
            if len(ans)<len(cur_find):
                ans = cur_find
            #case:abba
            cur_find = self.find_max_palindorme(s,index,index+1)
            if len(ans)<len(cur_find):
                ans = cur_find
        return ans
            
    #right往右走 left往左走
    def find_max_palindorme(self,s,left,right):
        while right<len(s) and left>=0 and s[right]==s[left]:
            right +=1
            left -=1
        #不match才跳出while 要return 上一組正確的
        return s[left+1:right]


if __name__ == '__main__':
    result = Solution()
    s = "afccfb"
    ans = result.longestPalindrome(s)
    print(ans)

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