寻找最长回文字符串

最长回文字符串（leetcode5）

这是晴天小猪无数次打开无数次尝试失败又无数次悻悻退出的玄学题目。然而今天的美团视频面试恰恰考了这道题，晴天小猪抓耳挠腮，还顺便抽了一张纸擤鼻涕，装模做样的分析和提出三种解决方案……

首先，晴天小猪根据刷字符串这一类型题的判断和直觉得出一个重大结论：

得用双指针！

晴天小猪想到三种双指针：

第一，快慢指针，类似与龟兔赛跑，通过比对龟和兔所在元素的值来判断是否满足回文的条件。
第二，头指针尾指针，一个在头，一个在尾，不停的比对不停的比对
第三，中心扩散法，如果元素个数为奇数，两个指针在一个中心同时向两边扩散；如果元素个数为偶数，两个指针在相邻的中心同时向两边扩散。

晴天小猪已经装模做样地分析出这三种方法，接下来我将用结果导向（就是我其实知道该用哪一个）的方法有一说一地分析了一遍…

如果用快慢指针的话可能会造成无法获取到最长字符串的要求，因为一旦快指针和慢指针成功比对成功，下一步是向后移动扩大边界，还是向内移动继续比对其他元素呢？

比如下面这种情况
```
acababacdb的最长回文字符串 
//当第一个a和第三个a比对成功后，是继续检查他们之间的元素是否是回文，还是继续前进。似乎都不能得到最后的结果…
```
- 1
- 2
头指针尾指针存在一个致命问题——两个指针移动的速度无法控制，虽然大多数情况下可能会设置相等。但是最长回文字符串的中心不一定就是原字符串的中心。
中心扩散法！，从中心向两端扩散的双指针技巧，避免了上述过程中对称元素匹配错误的问题，此外，对奇偶数的情况进行讨论。这样一来，既保证了检查回文的性质，又保证可以高效匹配直到两边元素不再是回文字符串中的元素为止。

代码如下（Swift实现）

func longestPalindrome(_ s: String) -> String {
    //判空
    if s.isEmpty {
        return ""
    }
    var lo = 0, hi = 0
    var chars = [Character](s)
    for (i,c) in chars.enumerated() {
    let len1 = palindrome(chars,i,i) //奇数个元素
    let len2 = palindrome(chars,i,i+1) //偶数个元素
    let maxLen = max(len1,len2) // 取最大
    if maxLen > hi - lo + 1 {
        lo = i - (maxLen - 1) / 2
        hi = i + maxLen / 2
    }
    }    
    return String(chars[lo...hi])
}
func palindrome(_ chars: [Character], _ l: Int, _ r: Int) -> Int {
    var l = l ,r = r
    while l >= 0 && r <= chars.count && chars[l] == chars[r] {
        l -= 1
        r += 1
    }
    return r - l - 1
}

最后，祝愿晴天小猪早日找到工作！！！

秒客网

寻找最长回文字符串

最长回文字符串（leetcode5）

相关文章