Question

925. 长按键入

English Version

题目描述

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

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

 

示例 1：

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

示例 2：

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

 

提示：

• 1 <= name.length, typed.length <= 1000
• name 和 typed 的字符都是小写字母

解法

方法一：双指针

class Solution:
  def isLongPressedName(self, name: str, typed: str) -> bool:
    m, n = len(name), len(typed)
    i = j = 0
    while i < m and j < n:
      if name[i] != typed[j]:
        return False
      cnt1 = cnt2 = 0
      c = name[i]
      while i + 1 < m and name[i + 1] == c:
        i += 1
        cnt1 += 1
      while j + 1 < n and typed[j + 1] == c:
        j += 1
        cnt2 += 1
      if cnt1 > cnt2:
        return False
      i, j = i + 1, j + 1
    return i == m and j == n

class Solution {
  public boolean isLongPressedName(String name, String typed) {
    int m = name.length(), n = typed.length();
    int i = 0, j = 0;
    for (; i < m && j < n; ++i, ++j) {
      if (name.charAt(i) != typed.charAt(j)) {
        return false;
      }
      int cnt1 = 0, cnt2 = 0;
      char c = name.charAt(i);
      while (i + 1 < m && name.charAt(i + 1) == c) {
        ++i;
        ++cnt1;
      }
      while (j + 1 < n && typed.charAt(j + 1) == c) {
        ++j;
        ++cnt2;
      }
      if (cnt1 > cnt2) {
        return false;
      }
    }
    return i == m && j == n;
  }
}

class Solution {
public:
  bool isLongPressedName(string name, string typed) {
    int m = name.size(), n = typed.size();
    int i = 0, j = 0;
    for (; i < m && j < n; ++i, ++j) {
      if (name[i] != typed[j]) return false;
      int cnt1 = 0, cnt2 = 0;
      char c = name[i];
      while (i + 1 < m && name[i + 1] == c) {
        ++i;
        ++cnt1;
      }
      while (j + 1 < n && typed[j + 1] == c) {
        ++j;
        ++cnt2;
      }
      if (cnt1 > cnt2) return false;
    }
    return i == m && j == n;
  }
};

func isLongPressedName(name string, typed string) bool {
  m, n := len(name), len(typed)
  i, j := 0, 0
  for ; i < m && j < n; i, j = i+1, j+1 {
    if name[i] != typed[j] {
      return false
    }
    cnt1, cnt2 := 0, 0
    c := name[i]
    for i+1 < m && name[i+1] == c {
      i++
      cnt1++
    }
    for j+1 < n && typed[j+1] == c {
      j++
      cnt2++
    }
    if cnt1 > cnt2 {
      return false
    }
  }
  return i == m && j == n
}