You are given a string s.
Your task is to remove all digits by doing this operation repeatedly:
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 <= 100s consists only of lowercase English letters and digits.This approach uses a stack data structure to solve the problem. A stack helps us easily keep track of and remove characters because of its LIFO (Last In, First Out) behavior. Here's the detailed plan:
At the end, the stack contains the result after all digits have been removed following the given rule.
This C solution uses an array to simulate a stack. The code iterates over the input string, and for each digit found, it pops the top character from the stack if available. For each non-digit, it pushes the character onto the stack. At the end, the stack contents are the result string.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the length of the string, because each character is processed once.
Space Complexity: O(n), in the worst case where all characters are non-digits, and they are stored in the stack.
This approach utilizes two pointers to effectively manage the character positions during the removal process without using a stack. It provides an intuitive way to keep track of characters to be removed as we traverse the string:
This C solution uses two index variables—one iterates over each character while the other builds the result string in place by moving non-digit characters and 'removing' digits by decrementing the non-digit index.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), processing each character a single time.
Space Complexity: O(1), in-place operations over the input string.
| Approach | Complexity |
|---|---|
| Stack-Based Approach | Time Complexity: O(n), where n is the length of the string, because each character is processed once. Space Complexity: O(n), in the worst case where all characters are non-digits, and they are stored in the stack. |
| Two-Pointer Approach | Time Complexity: O(n), processing each character a single time. Space Complexity: O(1), in-place operations over the input string. |
Clear Digits - Leetcode 3174 - Python • NeetCodeIO • 6,944 views views
Watch 9 more video solutions →Practice Clear Digits with our built-in code editor and test cases.
Practice on FleetCode