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 := 0
    for 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 = 0
        for i in range(len(s) - 1, -1, -1):
            if s[i].isdigit():
                cntDigit += 1
            elif cntDigit:
                cntDigit -= 1
            else:
                ans.append(s[i])
        return ''.join(reversed(ans))

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

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