3174. 清除数字

🟢   🔖  栈 字符串 模拟  🔗 力扣 LeetCode

题目

You are given a string s.

Your task is to remove all digits by doing this operation repeatedly:

• Delete the first digit and the closest non-digit character to its left.

Return the resulting string after removing all digits.

Example 1:

Input: s = "abc"

Output: "abc"

Explanation:

There is no digit in the string.

Example 2:

Input: s = "cb34"

Output: ""

Explanation:

First, we apply the operation on s[2], and s becomes "c4".

Then we apply the operation on s[1], and s becomes "".

Constraints:

• 1 <= s.length <= 100
• s consists only of lowercase English letters and digits.
• The input is generated such that it is possible to delete all digits.

题目大意

给你一个字符串 s 。

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

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

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

示例 1：

输入： s = "abc"

输出： "abc"

解释：

字符串中没有数字。

示例 2：

输入： s = "cb34"

输出： ""

解释：

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

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

提示：

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

解题思路

1. 初始化一个空栈 stack。
2. 遍历字符串 s 的每个字符 char：
   • 如果 char 是数字字符（0 <= char <= 9），则执行弹栈操作（若栈不为空）。
   • 否则，将该字符入栈。
3. 遍历结束后，将栈中的字符拼接为最终结果并返回。

复杂度分析

• 时间复杂度：O(n)，其中 n 为字符串的长度。每个字符处理一次。
• 空间复杂度：O(n)，在最坏情况下（没有数字）需要 O(n) 的栈空间。

代码

/**
 * @param {string} s
 * @return {string}
 */
var clearDigits = function (s) {
	let stack = [];
	for (let char of s) {
		if (char <= '9' && char >= '0') {
			if (stack.length) {
				stack.pop();
			}
		} else {
			stack.push(char);
		}
	}
	return stack.join('');
};