Leetcode第五题，判断最大回文子串，难度中等。（个人感觉在中等里算较难的）
题目描述：给你一个字符串 s，找到 s 中最长的回文子串。其中回文子串的定义为，从头或从尾开始读取，读取到的两个字符串相同。
首先，基础的验证回文串算法为：
假设给出的串中只包含字母
1
2
3
4
5
6
7
8
9
10
11
12
| var start = 0
var end = arr.count - 1
while(start < end){
if arr[start] != arr[end] {
return false
} else {
start += 1
end -= 1
}
}
return true
|
在解决本题时，若一个回文子串ababa为回文串,显然去掉首尾后子串bab也为回文串，由此可得状态转移方程dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])，从而使用动态规划算法解出最长的回文子串。
首先我们用一个二维数组来表示字符串中下标为i的字母，与下标为j的字母，加上他们之间的字符组成的子串是否为回文串。 显然当子串只有一个字符时必为回文串，所以初始化时我们将dp[i][i],i = 0..< s.count置为true。当原字符串的长度小于2时直接返回原字符，在这里我们考虑字符串长度大于二，也就是可能的回文子串最小长度为2的情况。
思路为：从2枚举到原字符串长度，每次循环中从i = 0开始枚举至s.count - 1,我们由L = j - i + 1, j为字符串右边界，i为字符串左边界，L为字符串长度，得出右边界j = L + i - 1，此时注意判断右边界是否溢出。接着由状态转移方程dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])，若此时首尾字符，即下标分别为i和j的字符不相等，则直接可以得出dp[i][j] = false, 反之，则分为此时子串长度小于4和不小于4两种情况，不小于4时dp[i][j] = dp[i+1][j-1]。至此，每种可能的子串是否为回文串已算出，记录下最大回文串的相关信息即可。
以下为代码（swift）：
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
45
46
47
48
49
50
| func longestPalindrome(_ s: String) -> String {
var str = Array(s)
if str.count < 2 {
return s
}
var maxLen = 1
var begin = 0
let temp = Array<Bool>.init(repeating: false, count: str.count)
var dp = Array<[Bool]>.init(repeating: temp, count: str.count)
for i in 0..<str.count {
dp[i][i] = true
}
// 动态转移方程 : dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])
for L in 2...str.count { //枚举每种子串长度的可能性，从2到原字符串长度
for i in 0..<str.count {
let j = L + i - 1 // 由 L = j - i + 1 得
if j >= str.count { // 子串右边界溢出，跳出本次循环
break
}
if str[i] != str[j] { // 判断首尾字符是否相等
dp[i][j] = false
} else { // 首尾字符相等时
// 若首尾字符相等，则由状态转移公式dp[i][j] = dp[i + 1][j - 1] && (s[i] == s[j])
if j-i < 3 { // j-i<3即L = 3,2,1,0. 当L=3时首尾字符相等即为回文串
dp[i][j] = true
} else { // 状态转移，此时该子串是否为回文串由dp[i+1][j-1]决定
dp[i][j] = dp[i+1][j-1]
}
}
// 如果dp[i][j] == true则为回文串，若大于当前最大回文串则记录下相关信息
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1
begin = i
}
}
}
var ret = ""
for index in begin..<begin + maxLen {
ret.append(str[index])
}
print(ret)
return ret
}
|
至此此题已解完。另外还可以有暴力遍历法、中心扩散法。
动态规划解法的时间复杂度为O(n^2),空间复杂度为O(n)
Tino Wu
