0125. 验证回文串 Valid Palindrome

问题描述

靠拢型双指针

这是一个典型的双指针问题, 相关介绍可以看这里.

close-up

#![allow(unused)]
fn main() {
// 靠拢型双指针
pub fn is_palindrome1(s: String) -> bool {
    // 根据题目要求, 过滤一下字符串
    let s: String = s
        .chars()
        .filter(char::is_ascii_alphanumeric)
        .map(|c| c.to_ascii_lowercase())
        .collect();
    if s.is_empty() {
        return true;
    }

    // 使用双指针来判断
    let mut left = 0;
    let mut right = s.len() - 1;
    let bytes = s.as_bytes();
    while left < right {
        if bytes[left] != bytes[right] {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}
}

当然也可以不过滤字符, 直接应用双指针:

#![allow(unused)]
fn main() {
// 靠拢型双指针, 但不对字符串预处理
pub fn is_palindrome2(s: String) -> bool {
    let chars: Vec<char> = s.chars().collect();
    if chars.is_empty() {
        return true;
    }

    let mut left = 0;
    let mut right = chars.len() - 1;
    while left < right {
        // 忽略非字符数字
        while left < right && !chars[left].is_ascii_alphanumeric() {
            left += 1;
        }
        // 忽略非字符数字
        while left < right && !chars[right].is_ascii_alphanumeric() {
            right -= 1;
        }

        if chars[left].to_ascii_lowercase() != chars[right].to_ascii_lowercase() {
            return false;
        }
        left += 1;
        right -= 1;
    }
    true
}
}

利用回文的特性

回文的特性就是, 把它反转过来, 会得到一样的结果.

我们只需要反转字符串, 并与原字符串对比一下就能确定, 它是不是回文.

reverse-string

#![allow(unused)]
fn main() {
// 使用回文字串的性质: 反转之后依然相同
pub fn is_palindrome3(s: String) -> bool {
    let s: String = s
        .chars()
        .filter(char::is_ascii_alphanumeric)
        .map(|c| c.to_ascii_lowercase())
        .collect();
    s.chars().rev().collect::<String>() == s
}
}

相关问题