5. Longest Palindromic Substring

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.

1
2
3
4
5
Example:
Input: "babad"
Output: "bab"

Note: “aba” is also a valid answer.

1
2
3
4
5
Example:
Input: "cbbd"
Output: "bb"

题目大意

最长的回文子字符串。

解题思路

遍历字符串,使用双指针的方式。
第一步:移动右指针找到第一个与左指针不相同的
第二步:移动左右指针,判断是否是回文数
第二步:判断是否是当前最大回文数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func longestPalindrome1(_ s: String) -> String {
let count = s.count
guard count > 1 else {
return s
}
var range = (start: Int, end: Int)(0, 0)
var chars = Array(s)
var i = 0
repeat {
var l = i - 1
var r = i + 1
while chars[i] == chars[r] {
r += 1
if r >= chars.count { break }
}
if l >= 0 && r < chars.count {
while chars[l] == chars[r] {
l -= 1
r += 1
if l < 0 || r >= chars.count { break }
}
}
i += 1
if range.end - range.start < r - 1 - (l + 1) {
range = (l + 1, r - 1)
}
}while i < count - 1 && (count - 1 - i) * 2 > range.end + 1 - range.start
return String(chars[range.start...range.end])
}
0%