最长回文子串的4种解法(swift实现)

一、问题

子串:原字符串中任意个连续字符组成的子序列,长度小于等于原字符串
回文:形如:”abba”, “abcdcba”等中间字符对称的文法
最长回文子串:某个字符串中满足回文特性的最长子串

二、解法

2.1 暴力查找

最先也最容易想到的解决办法,由于用到了三重for循环,时间复杂度为O(N^3),空间复杂度为O(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
31
func findLongestPalindrome_Normal(str: [String]) -> String {
var maxPalindromLength: Int = 0
var longestPalindrome: [String] = [String]()

for i in 0 ..< str.count {
for j in i+1 ..< str.count {
let len: Int = j-i
var subArray = [String]()
for k in i ..< j+1 {
subArray.append(str[k])
}
if isPalindrome(candidateStr: subArray) {
if maxPalindromLength < len {
maxPalindromLength = len
longestPalindrome = subArray
}
}
}
}
return longestPalindrome.joined()
}

// 判断是否回文字符串
func isPalindrome(candidateStr: [String]) -> Bool {
for i in 0 ..< candidateStr.count {
if String(candidateStr[i]) != String(candidateStr[candidateStr.count-1-i]) {
return false
}
}
return true
}

2.2 动态规划法

对于字符串str, 假设dp[i,j] == 1表示str[i…j]是回文子串,那么必定存在str[i+1,j-1] == 1,依次类推,最长回文子串就能分解成一系列的子问题,可以使用DP求解。

首先构建状态转移方程:

1
2
3
4
5
if(str[i] != str[j]) {
dp[i,j] = 0;
} else {
dp[i,j] = dp[i+1,j-1];
}

首先设定初始状态:

  • dp[i][i] = 1,即单个字符是回文串
  • if(str[i] == str[i+1]) dp[i][i+1] = 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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
func findLongestPalindrome_DP(str: [String]) -> String {
var maxLen = 1
var longestPalindromeString = ""
var dp = [[Int]](repeating: [Int](repeating: 0, count: str.count), count: str.count)

// 单个字符是回文串
for i in 0 ..< str.count {
dp[i][i] = 1
}

// 两个连续相同的字符也是回文串
for i in 0 ..< str.count-1 {
if str[i] == str [i+1] {
dp[i][i+1] = 1
maxLen = 2
var tmp = [String]()
tmp.append(str[i])
tmp.append(str[i+1])
longestPalindromeString = tmp.joined()
}
}

// 找出三个字符的回文串并以此类推
for k in 3 ... str.count {
for i in 0 ... str.count - k {
let j = i + k - 1
if str[i] == str [j] {
dp[i][j] = dp[i+1][j-1]
if dp[i][j] == 1 && maxLen < k {
maxLen = k
var tmp = [String]()
for m in i ..< j+1 {
tmp.append(str[m])
}
longestPalindromeString = tmp.joined()
}
}else {
dp[i][j] = 0
}
}
}

return longestPalindromeString
}

dp是存储状态的二维数组,很明显dp是一个上三角矩阵,但是swift中没有对应的数据结构,使用二维数组代替。
时间复杂度:O(N^2),空间复杂度:O(N^2)

2.3 中心扩展法

由于回文串具有对称性,因此,回文可以从它的中心展开,并且只有2n-1个这样的中心。

为什么会是 2n−1 个,而不是 n 个中心?
原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba”的中心在两个‘b’ 之间)。

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
func findLongestPalindrome_CenterExpand(str: [String]) -> String {
var start = 0
var end = 0
for i in 0 ..< str.count {
let len1 = self.expandAroundCenter(strArray: str, left: i, right: i)
let len2 = self.expandAroundCenter(strArray: str, left: i, right: i+1)
let len = max(len1, len2)
if len > end - start {
start = i - (len - 1) / 2
end = i + len / 2
}
}
var tmp = [String]()
for i in start ... end {
tmp.append(str[i])
}
return tmp.joined()
}

func expandAroundCenter(strArray: [String], left: Int, right: Int) -> Int {
var L = left
var R = right
while L >= 0 && R < strArray.count && strArray[L] == strArray[R] {
L = L - 1
R = R + 1
}
return R - L - 1
}

由于遍历字符串耗去O(N),围绕中心扩展回文串耗去O(N),因此时间复杂度为:O(N^2);
算法中没有使用额外的存储空间,空间复杂度为:O(1)。

2.4 Manacher

Manacher算法使用了一个非常巧妙技巧,只需扫描一遍字符串即可得到最长回文子串,其时间复杂度为O(N),这里不详细介绍了,感兴趣的同学可以去这里Manacher算法详细了解。