最长回文子串的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算法详细了解。