3174. Clear Digits
Description
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.
Solutions
Solution 1: Stack + Simulation
We use a stack stk
to simulate this process. We traverse the string s
. If the current character is a digit, we pop the top element from the stack. Otherwise, we push the current character into the stack.
Finally, we concatenate the elements in the stack into a string and return it.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of the string s
.
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 |
|