长按键入

发表于
本文字数： 1.2k 阅读时长 ≈ 1 分钟

LeetCode每日一题，925. Long Pressed Name

先看题目描述

B9anXV.png

大意就是一个人要在键盘中输入自己的名字，有的时候，某个字符可能被长按，即被输入多次，给定一个名字和一个被输入的字符串，问这个输入的字符串是否有可能是他的名字

算法和思路

思路就是使用两个指针，分别指向两个字符串中进行比较，若不相等则直接返回 false；否则就把两个指针都向后移动一位，若指向 name 的指针移动后指向字符不变，则继续比较两个指针对应字符，否则的话就将指向 typed 的指针移动到下一个不一样的字符

算法流程：

  • 初始化 i = 0，j = 0，m = name.length，n = typed.length
  • 若 m > n，则直接返回 false
  • 当 i < m 且 j < n时：
    • 若 name[i] 与 typed[j] 不相等，则直接返回 false
    • i 指针和 j 指针同时向后移动一位
    • 若 name[i] 与 name[i- 1] 不相等：
      • 则移动 j 指针指针 typed[j] 与 typed[j - 1] 不相等
  • 若 i = m，j = n，则返回 true；否则返回 false

算法源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int m = name.length();
        int n = typed.length();
        if (m > n) return false;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (name.charAt(i) != typed.charAt(j)) return false;
            i++;
            j++;
            if (i < m && name.charAt(i) == name.charAt(i - 1)) continue;
            while (j < n && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            }
        }
        return i == m && j == n;
    }
}