抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

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 查看具体过程。


0条评论

发表评论