LeetCode 3. 最长回文字串

作者: 笙绳省盛 | 来源:发表于2019-01-22 09:28 被阅读12次

    给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

    示例 1:
    输入: "babad"
    输出: "bab"
    注意: "aba" 也是一个有效答案。

    示例 2:
    输入: "cbbd"
    输出: "bb"

    为了避免在验证回文时进行不必要的重复计算。考虑 “ababa” 这个示例。如果我们已经知道
    “bab” 是回文,那么很明显,“ababa” 一定是回文,因为它的左首字母和右尾字母是相同的。因此,P(i,j)=(P(i+1,j−1) and Si==Sj)
    事实上,只需使用恒定的空间,我们就可以在 O(n2)的时间内解决这个问题。我们观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 2n−1 个这样的中心。
    为什么会是 2n−1 个,而不是 n 个中心?原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba” 的中心在两个 ‘b’ 之间)。

        func longestPalindrome(_ s: String) -> String {
            guard s.count > 1 else {
                return s
            }
            let array = Array(s)
            var start = 0
            var end = 0
            for i in 0..<s.count{
                var len1 : Int = expandAroundCenter(array: array, left: i, right: i)
                var len2 : Int = expandAroundCenter(array: array, left: i, right: i + 1)
                var len : Int = len1 > len2 ? len1 : len2
                if len > end - start{
                    start = i - (len - 1) / 2
                    end = i + len / 2
                }
            }
            
            return String(s[s.index(s.startIndex, offsetBy: start)...s.index(s.startIndex, offsetBy: end)])
            
        }
        
        func expandAroundCenter(array : [Character],left : Int,right : Int)->Int{
            var l = left
            var r = right
            while l >= 0 && r < array.count && array[l] == array[r]{
                l -= 1
                r += 1
            }
            return r - l - 1
        }
    

    相关文章

      网友评论

        本文标题:LeetCode 3. 最长回文字串

        本文链接:https://www.haomeiwen.com/subject/tcnkjqtx.html