一、问题
子串:原字符串中任意个连续字符组成的子序列,长度小于等于原字符串
回文:形如:”abba”, “abcdcba”等中间字符对称的文法
最长回文子串:某个字符串中满足回文特性的最长子串
二、解法
2.1 暴力查找
最先也最容易想到的解决办法,由于用到了三重for循环,时间复杂度为O(N^3),空间复杂度为O(1)。
1 | func findLongestPalindrome_Normal(str: [String]) -> String { |
2.2 动态规划法
对于字符串str, 假设dp[i,j] == 1表示str[i…j]是回文子串,那么必定存在str[i+1,j-1] == 1,依次类推,最长回文子串就能分解成一系列的子问题,可以使用DP求解。
首先构建状态转移方程:
1 | if(str[i] != str[j]) { |
首先设定初始状态:
- dp[i][i] = 1,即单个字符是回文串
- if(str[i] == str[i+1]) dp[i][i+1] = 1,即连续两个相同的字符是回文串
1 | func findLongestPalindrome_DP(str: [String]) -> String { |
dp是存储状态的二维数组,很明显dp是一个上三角矩阵,但是swift中没有对应的数据结构,使用二维数组代替。
时间复杂度:O(N^2),空间复杂度:O(N^2)
2.3 中心扩展法
由于回文串具有对称性,因此,回文可以从它的中心展开,并且只有2n-1个这样的中心。
为什么会是 2n−1 个,而不是 n 个中心?
原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba”的中心在两个‘b’ 之间)。
1 | func findLongestPalindrome_CenterExpand(str: [String]) -> String { |
由于遍历字符串耗去O(N),围绕中心扩展回文串耗去O(N),因此时间复杂度为:O(N^2);
算法中没有使用额外的存储空间,空间复杂度为:O(1)。
2.4 Manacher
Manacher算法使用了一个非常巧妙技巧,只需扫描一遍字符串即可得到最长回文子串,其时间复杂度为O(N),这里不详细介绍了,感兴趣的同学可以去这里Manacher算法详细了解。