0005. 最长回文子串 Longest Palindromic Substring

问题描述

这个问题, 要充分考虑回文字符串的特性:

• 如果回文字符串有奇数个字符, 那就以中间那个字符为分界, 左右两侧完全相同
• 如果回文字符串有偶数个字符, 那中间两个字符相同, 并且它们左右两侧也完全相同

基于这个特性, 可以利用双指针法来找出回文子串, 具体步骤是:

• 先遍历字符串中的每个字符
• 并以它为中心字符 (middle), 利用远离型双指针, 分别向左右两侧扩张, 并且 s[left] == s[right]
• 接下来考虑偶数个字符的情况, 以 (middle, middle + 1) 为中心, 利用远离型双指针, 分别向左右两侧扩张
• 通过这个循环, 就可以找出字符串 s 中的所有回文子串
• 然后保存下来最长的那个子串, 既是最终的结果

代码实现如下:

Rust

#![allow(unused)]
fn main() {
// 远离型双指针
pub fn longest_palindrome1(s: String) -> String {
    fn two_sides_equal(s: &str, left: usize, right: usize) -> bool {
        // 先检查两个索引值的有效性, 再比较它们指向的字符是否相等.
        right < s.len() && s.as_bytes().get(left) == s.as_bytes().get(right)
    }

    let mut longest_palindrome_len = 0;
    let mut longest_palindrome_start = 0;

    // 遍历所有字符
    for middle in 0..s.len() {
        // 以 (middle) 为对称点, substring 有奇数个字符
        let mut left = middle;
        let mut right = middle;
        while two_sides_equal(&s, left, right) {
            let length = right - left + 1;
            if longest_palindrome_len < length {
                longest_palindrome_len = length;
                longest_palindrome_start = left;
            }
            if left == 0 {
                break;
            }
            left -= 1;
            right += 1;
        }

        // 以 (middle, middle+1) 作为对称点, substring 有偶数个字符
        left = middle;
        right = middle + 1;
        while two_sides_equal(&s, left, right) {
            let length = right - left + 1;
            if longest_palindrome_len < length {
                longest_palindrome_len = length;
                longest_palindrome_start = left;
            }
            if left == 0 {
                break;
            }
            left -= 1;
            right += 1;
        }
    }

    // 返回结果
    s[longest_palindrome_start..longest_palindrome_start + longest_palindrome_len].to_owned()
}
}

Python

def longestPalindrome(s: str) -> str:
    # 跟据回文字符串的特性

    def twoSidesEqual(s: str, left: int, right: int) -> bool:
        # 先检查两个索引值的有效性, 再比较它们指向的字符是否相等.
        if left >= 0 and right < len(s) and s[left] == s[right]:
            return True
        else:
            return False

    longest_palindrome_len = 0
    longest_palindrome_start = 0

    # 遍历所有字符
    for middle in range(len(s)):
        # 以 (middle) 为对称点, substring 有奇数个字符
        left = middle
        right = middle
        while twoSidesEqual(s, left, right):
            length = right - left + 1
            if longest_palindrome_len < length:
                longest_palindrome_len = length
                longest_palindrome_start = left
            left -= 1
            right += 1

        # 以 (middle, middle+1) 作为对称点, substring 有偶数个字符
        left = middle
        right = middle + 1
        while twoSidesEqual(s, left, right):
            length = right - left + 1
            if longest_palindrome_len < length:
                longest_palindrome_len = length
                longest_palindrome_start = left
            left -= 1
            right += 1

    # 返回结果
    return s[longest_palindrome_start:longest_palindrome_start+longest_palindrome_len]

def main():
    s1 = "babad"
    out1 = longestPalindrome(s1)
    assert(out1 == "bab")

    s2 = "cbbd"
    out2 = longestPalindrome(s2)
    assert(out2 == "bb")

if __name__ == "__main__":
    main()