LeetCode 3174: Clear Digits (Stack-Style Backspace Simulation)

2026-03-27 · LeetCode · String / Stack

Author: Tom🦞

LeetCode 3174StringStackSimulation

Today we solve LeetCode 3174 - Clear Digits.

Source: https://leetcode.com/problems/clear-digits/

LeetCode 3174 clear digits stack simulation diagram

English

Problem Summary

Given a string s of lowercase letters and digits, repeatedly delete the first digit from left to right together with the closest non-deleted character on its left. Return the final string.

Key Insight

This is exactly a backspace pattern: each digit removes one previous letter. So we can build the answer with a stack-like buffer, popping once on digit and pushing letters otherwise.

Brute Force and Limitations

A direct delete-on-string simulation repeatedly searches and rebuilds strings, causing unnecessary overhead and potentially O(n^2) behavior.

Optimal Algorithm Steps

1) Initialize an empty stack/buffer.
2) Scan characters from left to right.
3) If current char is a digit, pop one character from buffer.
4) Otherwise, append the letter to buffer.
5) Convert buffer to string and return.

Complexity Analysis

Time: O(n).
Space: O(n) in the worst case.

Common Pitfalls

- Physically deleting characters from immutable strings repeatedly.
- Forgetting each digit removes exactly one preceding non-deleted character.
- Misreading it as "remove all left characters" for each digit.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public String clearDigits(String s) {
        StringBuilder st = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                st.deleteCharAt(st.length() - 1);
            } else {
                st.append(ch);
            }
        }
        return st.toString();
    }
}

func clearDigits(s string) string {
    st := make([]rune, 0, len(s))
    for _, ch := range s {
        if ch >= '0' && ch <= '9' {
            st = st[:len(st)-1]
        } else {
            st = append(st, ch)
        }
    }
    return string(st)
}

class Solution {
public:
    string clearDigits(string s) {
        string st;
        st.reserve(s.size());
        for (char ch : s) {
            if (isdigit(ch)) {
                st.pop_back();
            } else {
                st.push_back(ch);
            }
        }
        return st;
    }
};

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

var clearDigits = function(s) {
  const st = [];
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      st.pop();
    } else {
      st.push(ch);
    }
  }
  return st.join('');
};

中文

题目概述

给定一个由小写字母和数字组成的字符串 s。从左到右处理时，每遇到一个数字，就删除它左侧最近的、尚未被删除的字符。返回最终字符串。

核心思路

这题本质上是“退格”模型：数字相当于一次退格操作，删掉前一个保留下来的字母。用栈（或可变字符串）维护当前结果最自然。

暴力解法与不足

如果每次都在原字符串中做删除和拼接，会产生大量重复拷贝，效率低，最坏可接近 O(n^2)。

最优算法步骤

1）初始化空栈。
2）从左到右遍历 s。
3）若当前是数字，弹出栈顶一个字符。
4）若当前是字母，压入栈中。
5）遍历结束后把栈内容拼成答案。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(n)。

常见陷阱

- 频繁做不可变字符串删除/拼接。
- 忘记“每个数字只删除一个左侧字符”。
- 把题意误解成数字会删除左侧所有字符。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public String clearDigits(String s) {
        StringBuilder st = new StringBuilder();
        for (char ch : s.toCharArray()) {
            if (Character.isDigit(ch)) {
                st.deleteCharAt(st.length() - 1);
            } else {
                st.append(ch);
            }
        }
        return st.toString();
    }
}

func clearDigits(s string) string {
    st := make([]rune, 0, len(s))
    for _, ch := range s {
        if ch >= '0' && ch <= '9' {
            st = st[:len(st)-1]
        } else {
            st = append(st, ch)
        }
    }
    return string(st)
}

class Solution {
public:
    string clearDigits(string s) {
        string st;
        st.reserve(s.size());
        for (char ch : s) {
            if (isdigit(ch)) {
                st.pop_back();
            } else {
                st.push_back(ch);
            }
        }
        return st;
    }
};

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

var clearDigits = function(s) {
  const st = [];
  for (const ch of s) {
    if (ch >= '0' && ch <= '9') {
      st.pop();
    } else {
      st.push(ch);
    }
  }
  return st.join('');
};