Leetcode 5. 最长回文子串

5. 最长回文子串

解法一：暴力解法

思路：不断枚举每一个合法的字符区间

时间复杂度：O(N³) 空间复杂度：O(1)

class Solution {
    fun longestPalindrome(s: String): String {
        if (s.length < 2) return s
        var maxLen = 1
        var begin = 0

        val chars = s.toCharArray()
        for (i in chars.indices) {
            for (j in i + 1 until chars.size) {
                if (j - i + 1 > maxLen && validPalindrome(chars, i, j)) {
                    maxLen = j - i + 1
                    begin = i
                }
            }
        }
        return s.substring(begin, begin + maxLen)
    }

    private fun validPalindrome(chars: CharArray, i: Int, j: Int): Boolean {
        var left = i
        var right = j
        while (left < right) {
            if (chars[left] != chars[right]) return false
            left++
            right--
        }
        return true
    }
}

解法二：中心扩散法

思路：枚举所有的「回文中心」并尝试「扩展」，直到无法扩展为止，此时的回文串长度即为此「回文中心」下的最长回文串长度。

时间复杂度：O(N²) 空间复杂度：O(1)

class Solution {
    fun longestPalindrome(s: String): String {
        if (s.length < 2) return s
        var maxLen = 1
        var begin = 0

        val chars = s.toCharArray()
        for (i in 0 until chars.size - 1) {
            //奇数中心
            val oddLen = expandAroundCenter(chars, i, i)
            //偶数中心
            val evenLen = expandAroundCenter(chars, i, i + 1)

            val curMaxLen = Math.max(oddLen, evenLen)
            if (curMaxLen > maxLen) {
                maxLen = curMaxLen
                //覆盖奇偶两个情况
                begin = i - (maxLen - 1) / 2
            }
        }
        return s.substring(begin, begin + maxLen)
    }

    private fun expandAroundCenter(chars: CharArray, i: Int, j: Int): Int {
        val size = chars.size
        var left = i
        var right = j
        while (left >= 0 && right < size) {
            if (chars[left] == chars[right]) {
                left--
                right++
            } else {
                break
            }
        }
        //right - left + 1 - 2  （-2是因为需要减去最后那次不匹配的情况）
        return right - left - 1
    }
}

解法三：动态规划

1. 状态定义：dp[ i ][ j ]表示子串 s[ i .. j ]是否为回文子串
2. 状态转移方程：dp[ i ][ j ]=( s[ i ] == s[ j ] ) and dp[ i + 1 ][ j – 1 ]
3. 边界条件：
   对于长度为 1 的子串，它显然是个回文串；
   对于长度为 2 的子串，只要它的两个字母相同，它就是一个回文串。
   dp( i , i ) = true
   dp[ i , i + 1 ] = ( s[ i ] == s[ j ] )

整理后的最终状态方程：来源：Leetcode 官方

时间复杂度：O(N²) 空间复杂度：O(N²)

代码：

class Solution {
    fun longestPalindrome(s: String): String {
        if (s.length < 2) return s
        val len = s.length
        var maxLen = 1
        var begin = 0

        //表示 s[ i .. j ]是否是回文串
        val dp = Array(len) {
            BooleanArray(len) { false }
        }
        for (i in s.indices) {
            dp[i][i] = true
        }
        val chars = s.toCharArray()
        //i 行 j 列
        for (j in 1 until len) {
            for (i in 0 until j) {

                if (chars[i] != chars[j]) {
                    dp[i][j] = false
                } else {
                    if (j - i < 3) {
                        dp[i][j] = true
                    } else {
                        dp[i][j] = dp[i + 1][j - 1]
                    }
                }

                //只要 dp[i][j]=true，表示子串 s[i .. j]是回文，此时记录回文长度和起始位置
                if (dp[i][j] && j - i + 1 > maxLen) {
                    maxLen = j - i + 1
                    begin = i
                }
            }
        }

        return s.substring(begin, begin + maxLen)
    }

}

建议配合打印与 debug 查看具体过程。