How do I remove digits from a string in the 'Clear Digits' problem?

Use a stack-based approach: for each character, if it's a digit, remove the nearest non-digit character before it. Continue until all digits are removed.

What pattern does the 'Clear Digits' problem follow?

It follows a stack-based state management pattern where you manage characters from left to right, handling digits and non-digits efficiently.

How does stack management help solve the problem?

A stack helps keep track of non-digit characters and removes the nearest ones when a digit is encountered, ensuring the problem is solved efficiently.

What is the time complexity of solving the 'Clear Digits' problem?

The time complexity is O(n), where n is the length of the string, as each character is processed exactly once.

What are some common mistakes in solving this problem?

Mistakes include failing to properly mark digits for removal, not handling edge cases like no digits, and misunderstanding the string processing order.

#3174

Easy

auto_awesome栈·状态

LeetCode 题解工作台

清除数字

给你一个字符串 s 。你的任务是重复以下操作删除所有数字字符：删除第一个数字字符以及它左边最近的非数字字符。请你返回删除所有数字字符以后剩下的字符串。注意，该操作不能对左侧没有任何非数字字符的数字执行。示例 1：输入： s = "abc" 输出： "abc" 解释：字…

字符串栈模拟

题目描述

给你一个字符串 s 。

你的任务是重复以下操作删除所有数字字符：

删除 第一个数字字符 以及它左边最近的 非数字 字符。

请你返回删除所有数字字符以后剩下的字符串。

注意，该操作不能对左侧没有任何非数字字符的数字执行。

示例 1：

输入：s = "abc"

输出："abc"

解释：

字符串中没有数字。

示例 2：

输入：s = "cb34"

输出：""

解释：

一开始，我们对 s[2] 执行操作，s 变为 "c4" 。

然后对 s[1] 执行操作，s 变为 "" 。

提示：

1 <= s.length <= 100
s 只包含小写英文字母和数字字符。
输入保证所有数字都可以按以上操作被删除。

lightbulb

解题思路

方法一：栈 + 模拟

我们用一个栈 stk 来模拟这个过程，遍历字符串 s，如果当前字符是数字，就弹出栈顶元素，否则将当前字符入栈。

最后将栈中的元素拼接成字符串返回。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为字符串 s 的长度。

1

2

3

4

5

6

7

8

9

10

class Solution:
    def clearDigits(self, s: str) -> str:
        stk = []
        for c in s:
            if c.isdigit():
                stk.pop()
            else:
                stk.append(c)
        return "".join(stk)

speed

复杂度分析

指标	值
时间	O(n)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Candidate can effectively apply stack-based state management to solve the problem.
question_mark
Candidate is familiar with processing strings efficiently from left to right.
question_mark
Candidate can relate the stack operations to real-world scenarios or other algorithms.

warning

常见陷阱

外企场景

error
Forgetting to mark digits that should be removed or removing too many characters.
error
Not handling edge cases like no digits in the string or consecutive digits.
error
Misunderstanding the operation to apply on digits and non-digits in the string.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider strings with more complex patterns or large numbers of consecutive digits.
arrow_right_alt
Change the constraints by allowing uppercase letters or symbols in the string.
arrow_right_alt
Optimize for different input sizes or test for time efficiency in edge cases.

help

常见问题

外企场景

继续练习

#3412 计算字符串的镜像分数 #3561 移除相邻字符 #2696 删除子串后的字符串最小长度