leetcode:3174 清除数字 使用栈，时间复杂度O(n)

3174 清除数字

题目链接

题目描述

给你一个字符串 s 。

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

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

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

示例 1：

输入：s = "abc"
输出："abc"         
解释:字符串中没有数字。

示例 2：

输入：s = "cb34"
输出：""
解释：
一开始，我们对 s[2] 执行操作，s 变为 "c4" 。
然后对 s[1] 执行操作，s 变为 "" 。

题目解析

这道题目是一道字符串处理的题目，主要是删除所有数字字符，并且在删除数字字符后，删除它左边最近的非数字字符。

因此可以通过栈res记录结果，直接遍历数组，如果是数字字符，则跳过，并将res中的一个字符出栈，如果是非数字字符，则直接进行入栈操作，加入res中。

• 只需要一次遍历时间复杂度为O(n)。
• 空间复杂度O(n)。

代码实现

python版本：

class Solution(object):def clearDigits(self, s):res=""for i in range(0,len(s)):if s[i].isdigit():res = res[:-1]else:res+=s[i]return res

go版本：

func clearDigits(s string) string {var res []bytefor i:=0;i<len(s);i++{if s[i]<='9'&&s[i]>='0'{res = res[:len(res)-1]}else{res = append(res, s[i])}}return string(res)
}

C++版本：

class Solution {
public:string clearDigits(string s) {string res="";for(int i=0;i<s.size();i++){if(s[i]>='0'&&s[i]<='9'){res.pop_back();}else{res=res+s[i];}}return res;}
};