LeetCode 3174.清除数字：一个不用栈的方法

【LetMeFly】3174.清除数字：一个不用栈的方法

力扣题目链接：https://leetcode.cn/problems/clear-digits/

给你一个字符串 s 。

你的任务是重复以下操作删除 所有 数字字符：

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

请你返回删除所有数字字符以后剩下的字符串。

 

示例 1：

输出："abc"

解释：

字符串中没有数字。

示例 2：

输出：""

解释：

一开始，我们对 s[2] 执行操作，s 变为 "c4" 。

然后对 s[1] 执行操作，s 变为 "" 。

 

提示：

• 1 <= s.length <= 100
• s 只包含小写英文字母和数字字符。
• 输入保证所有数字都可以按以上操作被删除。

解题方法：计数 + 字符串翻转

一个数字可以抵消一个字母，因此使用一个整数$cntDigit$统计数字的个数。

倒着遍历字符串，遇到一个数字$cntDigit$就加一，遇到一个字符就尝试用数字抵消（如果$cntDigit$大于$0$则直接$cntDigit$减一，否则抵消不了，这个字符就需要加到字符串上）。

将字符串reverse，返回即可。

• 时间复杂度$O(len(s))$
• 空间复杂度：对于可变长字符串的编程语言：$O(1)$，因为力扣返回值不计入算法空间复杂度；对于不可变长字符串的编程语言：$O(len(s))$，可以开辟一个列表用来存放每一个字符串。

AC代码

C++

class Solution {
public:string clearDigits(string s) {string ans;int cntDigit = 0;for (int i = s.size() - 1; i >= 0; i--) {if (isdigit(s[i])) {cntDigit++;}else if (cntDigit) {cntDigit--;}else {ans += s[i];}}reverse(ans.begin(), ans.end());return ans;}
};

Go

package main
import "unicode"func clearDigits(s string) string {ansList := []rune{}cntDigit := 0for i := len(s) - 1; i >= 0; i-- {if unicode.IsDigit(rune(s[i])) {cntDigit++} else if cntDigit > 0 {cntDigit--} else {ansList = append(ansList, rune(s[i]))}}for i := 0; i < len(ansList) / 2; i++ {ansList[i], ansList[len(ansList) - i - 1] = ansList[len(ansList) - i - 1], ansList[i]}return string(ansList)
}

Java

class Solution {public String clearDigits(String s) {StringBuilder ans = new StringBuilder();int cntDigit = 0;for (int i = s.length() - 1; i >= 0; i--) {if (Character.isDigit(s.charAt(i))) {cntDigit++;}else if (cntDigit > 0) {cntDigit--;}else {ans.append(s.charAt(i));}}ans.reverse();return ans.toString();}
}

Python

class Solution:def clearDigits(self, s: str) -> str:ans = []cntDigit = 0for i in range(len(s) - 1, -1, -1):if s[i].isdigit():cntDigit += 1elif cntDigit:cntDigit -= 1else:ans.append(s[i])return ''.join(reversed(ans))

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

Tisfy：https://letmefly.blog.csdn.net/article/details/141943628