Keshawn_lu's Blog

Leetcode 925. 长按键入

双指针
字数统计: 491阅读时长: 2 min
2020/10/21 Share

题目简介：

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例 1：

1
2
3
输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

示例 2：

1
2
3
输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

示例 3：

1
2
输入：name = "leelee", typed = "lleeelee"
输出：true

示例 4：

1
2
3
输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。

提示：

  1. name.length <= 1000
  2. typed.length <= 1000
  3. name 和 typed 的字符都是小写字母。

思路：

定义两个指针，指向各自的字符串开头。

若指向的两个字符相同，则各往后移动一位。

若不相同，则判断name[i - 1]是否与typed[j]相同，若不相同，则返回false；若相同，则说明是多次输入的字符，将j持续往后移动，直至遇到不同的字符。

退出循环时，若typed还有字符未被遍历，则需要判断这些字符是否为多次输入的字符。

若name未遍历完全，则返回false。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    bool isLongPressedName(string name, string typed) {

        int i = 0;
        int j = 0;

        while(i < name.size() && j < typed.size()){

            if(name[i] == typed[j]){

                i++;
                j++;
            }
            else{

                if(name[i - 1] != typed[j])
                    return false;

                while(name[i - 1] == typed[j] && j < typed.size())
                    j++;
            }
        }

        while(j < typed.size()){

            if(typed[j] != typed[j - 1])    //检验剩余的字符是否为多次输入
                return false;
            j++;
        }

        return i == name.size();    //name需遍历完全
    }
};
CATALOG
  1. 1. 题目简介：
  2. 2. 思路：
  3. 3. 代码如下：
Total : 424
2023
2022
2021
2020
2019
动态规划 树 深度优先搜索 哈希表 数组 深度优先遍历 单调栈 字符串 双指针 栈 贪心 图 模拟 广度优先搜索 回溯 滑动窗口 二分查找 广度优先遍历 记忆化搜索 数学 链表 前缀和 双向链表 优先队列 拓扑排序 KMP 堆 字典树 递归 并查集 矩阵 位运算 双端队列 吴恩达团队NLP 吴恩达深度学习 线性表
杂谈 算法相关 PAT 2019推理小说阅读计划 NLP 深度学习 大三课程学习 大四课程学习 浙工商OJ 牛客网