0680. 验证回文串 II Valid Palindrome II

问题描述

在Rust中处理字符串, 远不如处理 Vec<u8> 或者 slice 简单, 所以这里我们在有必要时, 先把字符串 转换成数组: let bytes = s.as_bytes();

暴力法

利用题目中的要求, 按序依次跳过数组中的一个元素, 并判断它组成的新数组是不是回文.

remove-one-element

#![allow(unused)]
fn main() {
// 优化暴力法
// 计算超时, 无效
pub fn valid_palindrome2(s: String) -> bool {
    fn is_palindrome_slice(s: &[u8]) -> bool {
        let mut left = 0;
        let mut right = s.len() - 1;
        while left < right {
            if s[left] != s[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }

    let bytes = s.as_bytes();
    // 检查不跳过某一元素时的情况
    if is_palindrome_slice(bytes) {
        return true;
    }

    let mut new_bytes = bytes.to_vec();

    for i in 0..bytes.len() {
        // 跳过某一元素, 构造新的数组
        new_bytes.clear();
        new_bytes.extend_from_slice(&bytes[..i]);
        new_bytes.extend_from_slice(&bytes[i + 1..]);
        // 检查新构造出的数组
        if is_palindrome_slice(&new_bytes) {
            return true;
        }
    }
    false
}
}

这里的中间步骤, 每次都要构造一个新的数组. 而且新数组的大小与原来的数组基本是一样的. 对于有很多元素的数组来说, 遍历数组时, 每次的计算量并没有变化. 新数组的大小并没有快速收敛.

比如, 计算 s = "abcadecba", 可以看到每次循环它的计算量是不变的.

abcadecba
abcadecba
abcadecba
abcadecba
abcadecba
abcadecba
abcadecba
abcadecba
abcadecba

使用一个靠拢型双指针

这个是对暴力法的优化, 它完全不需要分配堆内存, 但思路是没有变的: 按序依次跳过数组中的一个元素, 并判断它组成的新数组是不是回文.

#![allow(unused)]
fn main() {
// 双指针法, 不需要分配新的堆内存
// 计算超时, 无效
pub fn valid_palindrome3(s: String) -> bool {
    let bytes = s.as_bytes();

    // 遍历数组, 用于跳过当前的一个元素,
    // 如果 i == bytes.len(), 则不跳过任何元素.
    for i in 0..=bytes.len() {
        // 使用靠拢型双指针来检查这个 slice 是不是回文.
        let mut left = 0;
        let mut right = bytes.len() - 1;

        let mut is_palindrome = true;
        while left < right {
            if left == i {
                left += 1;
                continue;
            }
            if right == i {
                right -= 1;
                continue;
            }

            if bytes[left] != bytes[right] {
                is_palindrome = false;
                break;
            }
            // 同时移动两个指针往中间靠拢.
            left += 1;
            right -= 1;
        }

        if is_palindrome {
            return true;
        }
    }

    false
}
}

这个优化基本无效的, 因为上面提到的核心问题没解决.

使用两个靠拢型双指针

这个是对上面方法的优化, 在外层遍历数组时, 也换成双指针法, 用于快速减少子数组中的元素个数. 这样可以 快速收敛, 这对于有大量元素的数组来说很有效.

#![allow(unused)]
fn main() {
// 使用两个靠拢型双指针, 不需要分配新的堆内存
pub fn valid_palindrome4(s: String) -> bool {
    fn is_palindrome(slice: &[u8], mut left: usize, mut right: usize) -> bool {
        while left < right {
            if slice[left] != slice[right] {
                return false;
            }
            left += 1;
            right -= 1;
        }
        true
    }

    let bytes = s.as_bytes();

    // 外层双指针, 用于遍历数组
    // 这里每次遍历, 就会减少子数组的长度, 这对于巨大的数组来说很关键.
    let mut left = 0;
    let mut right = bytes.len() - 1;
    while left < right {
        if bytes[left] != bytes[right] {
            return is_palindrome(bytes, left, right - 1) || is_palindrome(bytes, left + 1, right);
        }
        left += 1;
        right -= 1;
    }
    true
}
}

计算 s = "abcadecba", 可以看到, 其过程在快速收敛:

abcadecb
bcadec
cade
ad

相关问题