Easy

题目描述

给你一个字符串 s。

你的任务是通过重复执行以下操作来移除所有数字：

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

返回移除所有数字后的结果字符串。

注意：如果数字左边没有非数字字符，则无法对该数字执行操作。

示例 1：

输入：s = "abc"
输出："abc"
解释：
字符串中没有数字。

示例 2：

输入：s = "cb34"
输出：""
解释：
首先，我们对 s[2] 执行操作，s 变为 "c4"。
然后我们对 s[1] 执行操作，s 变为 ""。

约束条件：

  • 1 <= s.length <= 100
  • s 只包含小写英文字母和数字
  • 输入保证可以删除所有数字

解题思路

这道题要求我们删除所有数字，每次删除一个数字时，同时删除它左边最近的非数字字符。

方法一：栈模拟（推荐） 使用栈来模拟这个过程：

  • 遍历字符串，如果遇到非数字字符，将其压入栈中
  • 如果遇到数字，直接跳过（相当于删除），同时弹出栈顶元素（删除左边最近的非数字字符）
  • 最后栈中剩余的字符就是结果

这种方法的优势是能够自然地处理"最近的非数字字符"的要求，因为栈的后进先出特性正好符合"最近"的定义。

方法二：标记删除 按照提示的思路，从左到右遍历字符串，标记需要删除的字符，最后构建结果字符串。但这种方法需要额外的空间来标记，且实现稍复杂。

栈方法更直观简洁，是最优解法。

代码实现

class Solution {
public:
    string clearDigits(string s) {
        stack<char> st;
        
        for (char c : s) {
            if (isdigit(c)) {
                if (!st.empty()) {
                    st.pop();
                }
            } else {
                st.push(c);
            }
        }
        
        string result;
        while (!st.empty()) {
            result = st.top() + result;
            st.pop();
        }
        
        return result;
    }
};

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

public class Solution {
    public string ClearDigits(string s) {
        Stack<char> stack = new Stack<char>();
        
        foreach (char c in s) {
            if (char.IsDigit(c)) {
                if (stack.Count > 0) {
                    stack.Pop();
                }
            } else {
                stack.Push(c);
            }
        }
        
        return new string(stack.Reverse().ToArray());
    }
}

/**
 * @param {string} s
 * @return {string}
 */
var clearDigits = function(s) {
    const stack = [];
    
    for (let c of s) {
        if (/\d/.test(c)) {
            if (stack.length > 0) {
                stack.pop();
            }
        } else {
            stack.push(c);
        }
    }
    
    return stack.join('');
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度栈方法
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串的长度。时间复杂度为 O(n) 因为需要遍历整个字符串一次，空间复杂度为 O(n) 用于存储栈中的字符。