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%