5. Longest Palindromic Substring

[yunshuipiao]

5. Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

分析：求字符串的最长回文 子串(连续)

此题大概有4种解法：

a. 暴力求解

求出所有子串，判断是不是回文串， 并取长度最大者。

分析：

长度为1: n 个

长度为2: n - 1 个

….

长度为n, 1 个， 共计 n( n + 1) / 2， 乘上回文串的判断n， 时间复杂度为 O(n^3)

fun isPalindrome(s: String): Boolean {
    var l = 0
    var r = s.length - 1
    while (l <= r) {
        if (s[l] != s[r]) {
            return false
        }
        l += 1
        r -= 1
    }
    return true
}

b. 最长公共子串

此题目可以演变为 将 s 反转，求两个字符串的最长公共子串。

比如 abcdcb, 反转 字符串为 bcdcba, 最长公共子串为 bcdcb, 即结果。

这时可使用动态规划， 使用一个二维数组来记录， map[i][j]表示 s 和 s1 两个字符串在 s[0, i] 和 s1[0, j] 两个字符串的最长公共子串。

   b  c  d  c  d  a
a  0  0  0  0  0  1  
b  1  0  0  0  1  0  
c  0  2  0  1  0  0  
d  0  0  3  0  0  0  
c  0  1  0  4  0  0  
b  1  0  0  0  5  0  

上述就是求的的二维数组，在 O(n^2) 的时间复杂度得到 map 的值, 当 map[i][j] 的值大于当前结果的长度时，保存当前结果。比如上述的 map[5][4] 的值最大， 即可得到结果。

result = s.subString(i - map[5][4] + 1, i + 1)

fun longCommonSubString(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    val rs = s.reversed()
    val map = Array(s.length) { Array(s.length) { 0 } }
    for (i in 0 until s.length) {
        for (j in 0 until rs.length) {
            if (s[i] == rs[j]) {
              // 边界条件
                if (i - 1 < 0 || j - 1 < 0) {
                    map[i][j] = 1
                } else {
                    map[i][j] = map[i - 1][j - 1] + 1
                }
            } else {
                map[i][j] = 0
            }
            if (map[i][j] > result.length) {
                val temp = s.substring(i - map[i][j] + 1, i + 1)
              	// 得出最长结果，判断回文串
                if (isPalindrome(temp)) {
                    result = temp
                }
            }
        }
    }
    return result
}

注意

还有一种情况， aacdefdcaa 字符串，由于其反转字符串与其的 最长公共子串 为 aac, 不满足条件。

由于 aac 的反转字符串也在其中，所以在上面的过程中，保存当前结果之前，还有判断当前是不是回文串。

时间复杂度 O(n^3), 空间复杂度 O(n^2)

c. 动态规划

由于回文串的性质，由于 s[i] == s[j] 并且 s[i + 1, j + 1] 是回文串，那么 s[i, j] 也是回文串。

所以可以使用一个二维数组来记录， map[i][j] , 表示 s[i, j] 是不是回文串。

1  0  0  0  0  0  
0  1  0  0  0  1  
0  0  1  0  1  0  
0  0  0  1  0  0  
0  0  1  0  1  0  
0  1  0  0  0  1

是得出的二维数组，对角线表示当前字符，为回文串。

map[1][5] 为1， 表示 s[1, 5] 是回文串。取最大值即可。

时间复杂度为 O(n^2)

fun dp(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    val map = Array(s.length) { Array(s.length) { 0 } }
    for (i in 0 until map.size) {
        for (j in 0 until map[0].size) {
            if (s[j] == s[i]) {
                if (i - j <= 1) {
                    map[j][i] = 1
                } else if (map[j + 1][i - 1] == 1) {
                    map[j][i] = 1
                }
            }
            if (map[j][i] == 1 && i - j + 1 >= result.length) {
                result = s.substring(j, i + 1)
            }
        }
    }
    return result
}

d. 最佳判断法

根据回文串的性质，遍历字符串，分别求 s[i] 为中心点，s[i, j] 为中心点的字符串的最长子回文串。

比如 abcdcb:

a 为中心点：结果为 a

ab 为中心点， 结果为 ""

...

d 为中心点， 结果 bcdcb；

dc 为中心点， 结果 ""；

fun bestMethod(s: String): String {
    if (s.isBlank()) {
        return s
    }
    var result = ""
    for (i in 0 until s.length) {
       // 以 s[i] 为中心进行计算
        val len1 = getPalindromeLen(s, i, i)
        if (len1 >= result.length) {
            result = s.substring(i - len1 / 2, i + len1 / 2 + 1)
        }
      	// 以 s[i，j] 为中心进行计算
        val len2 = getPalindromeLen(s, i, i + 1)
        if (len2 >= result.length) {
            result = s.substring(i - len2 / 2 + 1, i + len2 / 2 + 1)
        }
    }
    return result
}

/**
 * 判断回文串, 并返回最大长度
 */
fun getPalindromeLen(s: String, i: Int, j: Int): Int {
    var l = i
    var r = j
    while (l >= 0 && r < s.length) {
        if (s[l] == s[r]) {
            l -= 1
            r += 1
        } else {
            break
        }
    }
    return r - l - 1
}

Test code

@Test
fun _0005() {
//    var str = "aacdefdcaa"
    var str = "abcdcb"
    val result = dp(str)
    println(result)
}