What is the best approach for the Long Pressed Name problem?

Using two-pointer scanning with invariant tracking ensures each character in typed aligns with the name or a valid long press.

Can this problem be solved recursively?

While recursion is possible, it complicates handling consecutive repeated characters and increases space usage unnecessarily.

How do I handle characters repeated multiple times in typed?

Advance the typed pointer while the character matches the previous name character; only advance the name pointer when characters match exactly.

What if typed has extra characters not in name?

If a character in typed neither matches the current nor the previous character in name, return false immediately.

Does GhostInterview explain failure modes for this problem?

Yes, it highlights skipped name characters and invalid long presses that often cause incorrect outputs in interviews.

#925

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

长按键入

你的朋友正在使用键盘输入他的名字 name 。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。你将会检查键盘输入的字符 typed 。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True 。示例 1：输入： name = "alex"…

双指针字符串

题目描述

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

lightbulb

解题思路

方法一：双指针

我们利用两个指针 $i$ 和 $j$ 分别指向字符串 $\textit{typed}$ 和 $\textit{name}$ 的第一个字符，然后开始遍历，如果 $\textit{typed}[j] \neq \textit{name}[i]$ ，说明两个字符串不匹配，直接返回 $\textit{False}$ 。否则，我们找到连续相同的字符的下一个位置，分别记为 $x$ 和 $y$ ，如果 $x - i > y - j$ ，说明 $\textit{typed}$ 中的字符个数小于 $\textit{name}$ 中的字符个数，直接返回 $\textit{False}$ 。否则，我们将 $i$ 和 $j$ 更新为 $x$ 和 $y$ ，继续遍历，直到 $i$ 和 $j$ 分别遍历完 $\textit{name}$ 和 $\textit{typed}$ ，返回 $\textit{True}$ 。

时间复杂度 $O(m + n)$ ，其中 $m$ 和 $n$ 分别是字符串 $\textit{name}$ 和 $\textit{typed}$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

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
            x = i + 1
            while x < m and name[x] == name[i]:
                x += 1
            y = j + 1
            while y < n and typed[y] == typed[j]:
                y += 1
            if x - i > y - j:
                return False
            i, j = x, y
        return i == m and j == n

speed

复杂度分析

指标	值
时间	complexity is O(n + m) where n and m are the lengths of name and typed because each pointer scans its string once. Space complexity is O(1) as no extra data structures are used beyond pointer variables.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Expect linear scanning solutions rather than nested loops.
question_mark
Check edge cases like repeated characters at the start or end of typed.
question_mark
Clarify whether empty strings or single-character names are possible inputs.

warning

常见陷阱

外企场景

error
Assuming all repeated characters are valid without matching the name sequence.
error
Failing to check the final position of the name pointer after traversal.
error
Ignoring consecutive repeated characters at the start or end of typed.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allow uppercase letters and consider case-sensitive matching.
arrow_right_alt
Count minimal number of long presses required to produce typed from name.
arrow_right_alt
Check if typed can result from name with both long presses and skipped characters.

help

常见问题

外企场景

继续练习

#917 仅仅反转字母 #942 增减字符串匹配 #844 比较含退格的字符串