925. 长按键入

🟢   🔖  双指针 字符串  🔗 力扣 LeetCode

题目

Your friend is typing his name into a keyboard. Sometimes, when typing a character c, the key might get long pressed , and the character will be typed 1 or more times.

You examine the typed characters of the keyboard. Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

Example 1:

Input: name = "alex", typed = "aaleex"

Output: true

Explanation: 'a' and 'e' in 'alex' were long pressed.

Example 2:

Input: name = "saeed", typed = "ssaaedd"

Output: false

Explanation: 'e' must have been pressed twice, but it was not in the typed output.

Constraints:

• 1 <= name.length, typed.length <= 1000
• name and typed consist of only lowercase English letters.

题目大意

你的朋友正在使用键盘输入他的名字 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 的字符都是小写字母

解题思路

可以通过双指针法来解决问题。

1. 定义双指针

   • 用指针 i 遍历字符串 name，用指针 j 遍历字符串 typed。

2. 匹配字符

   • 当 name[i] == typed[j] 时，表示当前字符匹配，i 和 j 同时向右移动。
   • 如果字符不匹配，检查 typed[j] == typed[j - 1] 是否成立。如果成立，则表示当前字符是长按输入，继续移动 j。
   • 如果都不满足，直接返回 false。

3. 验证剩余字符

   • 遍历结束后，可能会有多余的长按字符未处理，需要检查 typed 中剩余的字符是否和最后一个字符相同。

4. 验证是否匹配

   • 只有当 i == name.length 且 j == typed.length 时，返回 true，否则返回 false。

复杂度分析

• 时间复杂度：O(m + n)，其中 n, m 分别是 name 和 typed 的长度，两个指针分别遍历 name 和 typed。
• 空间复杂度：O(1)，使用了常量级别的额外空间。

代码

/**
 * @param {string} name
 * @param {string} typed
 * @return {boolean}
 */
var isLongPressedName = function (name, typed) {
	const m = name.length;
	const n = typed.length;
	let i = 0,
		j = 0;

	while (i < m && j < n) {
		if (name[i] === typed[j]) {
			i++;
			j++;
		} else if (j > 0 && typed[j] === typed[j - 1]) {
			j++;
		} else {
			return false;
		}
	}

	// 检查剩余的长按字符
	while (j < n && typed[j] === typed[j - 1]) {
		j++;
	}

	// 判断两个字符串是否都遍历完
	return i === m && j === n;
};

相关题目

题号	标题	题解	标签	难度	力扣
2410	运动员和训练师的最大匹配数	[✓]	贪心 数组 双指针 1+	🟠	🀄️ 🔗