0925. 长按键入 Long Pressed Name

问题描述

并行双指针

典型的并行双指针问题.

typed 数组与 name 数组不一致的情况有三种:

• 长按了, 通过 name[index1 - 1] == typed[index2] 来确认
• 按错了, name[index1] != typed[index2]
• 少按了, 在最后, index2 != len2

要注意的是:

• 如果已经遍历完 name 数组, 要检查 typed 数组有没有遍历完
• 返回 true 的条件就是两个数组都满足条件的情况下遍历完

#![allow(unused)]
fn main() {
// 并行双指针
pub fn is_long_pressed_name1(name: String, typed: String) -> bool {
    assert!(!name.is_empty() && !typed.is_empty());
    let name = name.as_bytes();
    let typed = typed.as_bytes();
    let len1 = name.len();
    let len2 = typed.len();

    // 初始化两个指针
    let mut index1 = 0;
    let mut index2 = 0;

    // 使用双指针遍历两个数组.
    while index1 < len1 && index2 < len2 {
        if name[index1] == typed[index2] {
            // 相等时, 同时向前移动两个指针.
            index1 += 1;
            index2 += 1;
        } else if index1 > 0 && name[index1 - 1] == typed[index2] {
            // 长按了一下
            index2 += 1;
        } else {
            // 按错了
            return false;
        }
    }

    // 如果已经遍历完了 name 数组, 还没遍历完 typed 数组,
    // 接下来遍历 typed 里剩下的元素.
    // 遍历的唯一条件就是 typed 里面剩下的元素都和 name 数组最后一个元素相同,
    // 否则就是按错了.
    while index2 < len2 && name[len1 - 1] == typed[index2] {
        index2 += 1;
    }

    // 检查两个数组是否都遍历完, 如果没有遍历完:
    // - index1 < len1, 少按了
    // - index2 < len2, 按错了
    index1 == len1 && index2 == len2
}
}