051 · Clear Digits
My First Thoughts
嗯，这个继承前几道题继续的。
前几道题一直在处理这种“读到一个新字符，就看看它要不要和前面最近留下来的字符发生关系”的问题。
这一题本质还是一个 waiting_list。
如果当前字符不是数字，就放进去。
如果当前字符是数字，就移除 waiting_list 最后一个字符。
因为题目说：每个数字都要删除它左边最近的一个非数字字符。
而从左到右遍历时，waiting_list 里保存的就是当前还没有被删除的字母。它的最后一个元素，正好就是当前数字左边最近、还留下来的那个字符。
所以整体没有很复杂。
一开始大概会写成：
waiting_list = []
for char in s:
if waiting_list and char in range(0, 10):
waiting_list.pop()
else:
waiting_list.append(char)
return "".join(waiting_list)想法是对的：用 waiting_list 保存还没删除的字符，遇到数字就删掉最后一个。
Why That Is Not Enough
这里主要不是算法问题，而是 Python 里的类型细节。
遍历字符串时：
for char in s:拿到的 char 是一个字符串字符。
比如：
char = "3"但这句：
char in range(0, 10)是在问：字符串 "3" 是不是在整数 0, 1, 2, ..., 9 里面。
答案永远是 False，因为 "3" 和整数 3 不是同一个东西。
所以数字字符不会被识别出来，代码会把 "3"、"4" 也加入 waiting_list，最后结果就不对了。
这里应该用字符串自己的判断方法：
char.isdigit()它判断的是：当前这个字符是不是数字字符。
另外，题目保证输入可以删除所有数字，所以遇到数字时，左边一定有可以删除的字母。代码里可以直接：
waiting_list.pop()Final Idea
继续使用原来的 waiting_list。
它表示：当前已经处理过的字符里，还没有被删除的那些字母。
从左到右遍历 s：
- 如果
char是字母，就加入waiting_list - 如果
char是数字，就删除waiting_list的最后一个字符
最后，waiting_list 里剩下的字符就是答案。
和前几题相比，变化只有一个：这次不是判断“当前字符能不能和栈顶配对”，而是当前字符本身如果是数字，就主动删除它左边最近留下来的字母。
这个“最近留下来的字母”，正好就是 waiting_list[-1]。
Why It Works
题目每次要删除的是：
当前最靠左的数字，以及它左边最近的一个非数字字符。
从左到右处理字符串时，当我们遇到一个数字，说明它就是当前还没处理过的最靠左数字。
在它左边，已经处理过但还没有被删除的字母，都保存在 waiting_list 里。
这些字母的顺序和原字符串中的顺序一致，所以 waiting_list 的最后一个字符，就是这个数字左边最近的、仍然存在的非数字字符。
因此遇到数字时执行：
waiting_list.pop()就等价于删除数字左边最近的那个非数字字符。
数字本身也不加入 waiting_list，相当于这个数字也被删除了。
如果遇到的是字母，它暂时没有被删除，就应该保留下来：
waiting_list.append(char)比如：
s = "abc12"先读到 "a", "b", "c"，都加入 waiting_list：
["a", "b", "c"]读到 "1"，删除最后一个 "c"：
["a", "b"]读到 "2"，删除最后一个 "b"：
["a"]最后拼回字符串，就是：
"a"Code
def clearDigits(s):
waiting_list = []
for char in s:
if char.isdigit():
waiting_list.pop()
else:
waiting_list.append(char)
return "".join(waiting_list)Complexity
| Time | \(O(n)\) - n 是 s 的长度；每个字符只处理一次 |
| Space | \(O(n)\) - 最坏情况下没有数字，waiting_list 会保存所有字符 |
Takeaway
当题目要求删除“左边最近还留下来的元素”时，可以把还没被删除的元素放进一个列表。列表末尾就是最近的那个元素。注意在 Python 里，字符串里的数字是字符，比如
"3"，不是整数3；判断数字字符要用char.isdigit()。
← Quiz