[ LeetCode ] 5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思路: DP
http://yumodev.com/2016/08/16/leetcode-5-LongestPalindrome.html

https://www.youtube.com/watch?v=Fi5INvcmDos

Time: O(n^2)

Space: O(n^2)

1. 起一個 2 維 矩陣 dp, dp[start][end] 表示 s[start][end] 是否為 迴文

假設字串 為 "babad"






我們可以看到從左上到右下 都為 1 (True), 因為子字串
"b"
"a"
"b"
"a"
"b"
都只有一個字 所以一定是 迴文 (line 14)

2. 接者如何判斷一個子字串是否是迴文呢?
假設現在要判斷 "babab" 是否是迴文, 我們可以拆成兩步,
a) 字串 頭尾是不是相等 (line 18)

b) 中間的子串 在這裡是 "aba" 是否為迴文 (line 16). 上面黃色的位置
    另外 如果現在要判斷的字串長度等於 2. 比方說 "bb" 這裡因為沒有中間的子串
    所以直接算是 True (line 17)

3. 每次字串被判定為 迴文的時候 就比較一下現在最長的字串