切换主题
回文问题篇
回文子串
中心扩散法！
JavaScript
const countSubstrings = s => {
const len = s.length
let cnt = 0
for (let idx = 0; idx < 2 * len - 1; idx++) {
let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
while (i >= 0 && j < len) {
if (s.charAt(i) !== s.charAt(j)) break
cnt++
i--
j++
}
}
return cnt
}时间复杂度：O(n^2)；空间复杂度：O(1)。
最长回文子串
中心扩散法！
JavaScript
const longestPalindrome = s => {
const len = s.length
let max = start = end = 0
for (let idx = 0; idx < 2 * len - 1; idx++) {
let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
while (i >= 0 && j < len) {
if (s.charAt(i) !== s.charAt(j)) break
if (j - i > max) {
max = j - i
start = i
end = j
}
i--
j++
}
}
return s.substring(start, end + 1)
}时间复杂度：O(n^2)；空间复杂度：O(1)。
分割回文串
分割回文串 II
- 状态定义：
dp[i] = x，表示s[0]至s[i-1]的最小切割次数为x； base case：dp[0] = -1；- 状态转移方程：
dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1)。
JavaScript
const minCut = s => {
const len = s.length
const dp = Array(len + 1).fill(Infinity)
dp[0] = -1
for (let idx = 0; idx < 2 * len - 1; idx++) {
let [i, j] = [idx >> 1, (idx >> 1) + (idx & 1)]
while (i >= 0 && j < len) {
if (s.charAt(i) !== s.charAt(j)) break
dp[j + 1] = Math.min(dp[j + 1], dp[i] + 1)
i--
j++
}
}
return dp[len]
}时间复杂度：O(n^2)；空间复杂度：O(n)。