LeetCode-5.最长回文子串

发表于 分类于

题目描述

给你一个字符串 s，找到 s 中最长的回文子串。

1
2
3
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
1
2
输入：s = "cbbd"
输出："bb"

提示：

  • 1 <= s.length <= 1000
  • s 仅由数字和英文字母组成

题解

方法1

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
func longestPalindrome(_ s: String) -> String {
  guard !s.isEmpty else {
    return ""
  }
  func searchAround(_ array: [String], _ left: Int, _ right: Int) -> Int {
    var begin = left
    var end = right
    while begin >= 0 && end < array.count && array[begin] == array[end] {
      begin -= 1
      end += 1
    }
    
    return end - begin - 1
  }
  
  var left = 0
  var right = 0
  let array = s.map({ String.init($0)}) // 转成数组处理效率更高

  for i in 0 ..< array.count {
    let length1 = searchAround(array, i, i)
    let length2 = searchAround(array, i, i + 1)
    let length = max(length1, length2)
    if length > right - left + 1 {
      left = i - (length - 1) / 2
      right = i + length / 2
    }
  }
  return array[left ... right].joined()
}

方法2

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
32
33
34
35
36
37
38
func longestPalindrome2(_ s: String) -> String {
  guard !s.isEmpty else {
    return ""
  }
  var begin = 0
  var end = 0
  
  let array = s.map({ String($0) })
  
  for index in 0 ..< array.count {
    let (left1, right1) = helper(array, index, index)
    let (left2, right2) = helper(array, index, index + 1)
    let length1 = right1 - left1
    let length2 = right2 - left2
    
    let curMax = max(length1, length2)
    if curMax > end - begin {
      if curMax == length1 {
        (begin, end) = (left1, right1)
      } else {
        (begin, end) = (left2, right2)
      }
    }
  }
  
  return array[begin ... end].joined()
}

func helper(_ arr: [String], _ left: Int, _ right: Int) -> (Int, Int) {
  var begin = left
  var end = right
  while begin >= 0 && end < arr.count && arr[begin] == arr[end] {
    begin -= 1
    end += 1
  }
  
  return (begin + 1, end - 1)
}