LeetCode 5. Longest Palindromic Substring
2022.08.27
問題
https://leetcode.com/problems/longest-palindromic-substring/description/
typescript
function longestPalindrome(s: string): string {
if (!s || s.length <= 1) return s
let longest = s.substring(0, 1)
for (let i = 0; i < s.length; i++) {
let left = i
let right = i
while (left >= 0 && right < s.length && s[left] === s[right]) {
left -= 1
right += 1
}
const oddPalindrome = s.slice(left + 1, right)
left = i
right = i + 1
while (left >= 0 && right < s.length && s[left] === s[right]) {
left -= 1
right += 1
}
const evenPalindrome = s.slice(left + 1, right)
if (Math.max(oddPalindrome.length, evenPalindrome.length) > longest.length) {
longest = oddPalindrome.length > evenPalindrome.length ? oddPalindrome : evenPalindrome
}
}
return longest
}
- 回文には、奇数の長さになるものと偶数の長さになるものがある
- 最初の文字に対して、左に右に1文字ずつ同じかどうか確認しながら、増やしていく