[LeetCode] 5. Longest Palindromic Substring

轉自LeetCode

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"

<Solution>

這題有 DP 解法，也有專門算 palindromic substring 長度的演算法，叫 Manacher's Algorithm

DP 的想法是，用 dp[i][j]  表示從 s[i] 到 s[j] 是否是一個回文串

其公式如下：

當 s[i] = s[j] 的時候，如果是相鄰字元 (j - i < 2)，則 dp[i][j] = true

當 s[i] = s[j] 的時候，如果不是相鄰字元 (j - i >= 2)，則 dp[i][j] = dp[i+1][j-1]

當 s[i] != s[j] 的時候，則 dp[i][j] = false

code 如下

kotlin

演算法說明 : ref1、ref2

使用 Manacher's Algorithm 來解這題，可以在 O(n) 裡面解完

C++
Java