5. 最长回文子串

作者: 花果山松鼠 | 来源:发表于2018-07-13 14:18 被阅读2次

    一、题目原型:

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

    二、题目意思剖析:

    回文其实是对称的一个字符串。
    比如:aba 、xyx、 mnnm、xoox 这样子。。。

    输入: "babad"
    输出: "bab"
    注意: "aba"也是一个有效答案。
    
    输入: "cbbd"
    输出: "bb"
    

    三、解题思路:

    中心法

    官方解释:
    事实上,只需使用恒定的空间,我们就可以在 O(n^2) 的时间内解决这个问题。
    我们观察到回文中心的两侧互为镜像。因此,回文可以从它的中心展开,并且只有 2n−1 个这样的中心。
    你可能会问,为什么会是 2n−1 个,而不是 n 个中心?原因在于所含字母数为偶数的回文的中心可以处于两字母之间(例如 “abba” 的中心在两个 ‘b’ 之间)。

    我的理解:
    我们根据对称的这个特性,来进行查找,以一个点为中心,两个指针左右移动,如果两边对应的字母相同,那么就继续移动,直到超出边界或者两边字母不同。

    安排: 笔记思路.JPG
    // 返回当前回文最大的长度
    func haha(_ letters: [String],_ left: Int, _ right: Int) -> (Int) {
        
        var L:Int = left
        var R: Int = right
        
        // 当左边指针不小于0,当右边指针不超过字符串长度
        // 并且左右两个数值要相等
        while L>=0 && R<letters.count && letters[L] == letters[R] {
            L = L - 1
            R = R + 1
        }
        return R - L - 1
    }
    
    func longestPalindrome(_ s: String) -> String {
        
        var letters: [String] = []
        for char in s {
            let str: String = String.init(char)
            letters.append(str)
        }
        
        var start:Int = 0
        var end: Int = 0
        var huiwen: String = ""
        for i in 0..<letters.count {
            
            // 这分为两种情况:1.回文长度为奇数时,中心在中间那个字母
            //              2.回文长度为偶数时,中心在两个字母之间
            let len1: Int = haha(letters, i, i)
            let len2: Int = haha(letters, i, i+1)
            // 取最大值
            let len: Int = len1 > len2 ? len1 : len2
            
            if len > end - start {
                start = i - (len - 1) / 2
                end = i + len / 2
            }
        }
        
        for i in start..<end+1 {
            huiwen.append(letters[i])
        }
        return huiwen
    }
    

    四、小结

    一切一切的算法,前提是要找到规律。然后一步一步剖析找出最好的算法。
    在本题中,我的笔记思路只画出了一种情况,还有另一种情况就是回文长度为偶数时,中心在两个字母之间,也是一样的规律去找。最后比较这两种情况,找出最大值就行了。

    总提交数.png 提交结果.png

    有其他好的方法请极速留言,非常乐意一起探讨。😄

    相关文章

      网友评论

        本文标题:5. 最长回文子串

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