力扣No.3174 删除数字题解

题目描述

给你一个字符串 s 。

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

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

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

示例 1：

输入：s = "abc"

输出："abc"

解释：

字符串中没有数字。

示例 2：

输入：s = "cb34"

输出：""

解释：

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

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

提示：

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

问题解析

先分析下问题，本题的要求是删除字符串中的数字字符以及其左边的第一个字符。

在偷瞄答案使用栈处理之前，我考虑过通过组合新字符的方式来解决问题，但是实际上这个方法需要考虑的因素太多了。

大概的思路是通过遍历字符串，当遍历到数字字符时不做处理，遍历到其他字符存入新字符，但是这样存在的问题是在新字符中删除数字字符对应的左边字符还需要一次处理，如果新建一个索引表又会导致更多的内存开销，而且还有一个需要考虑的情况是，需要删除的字符可能与数字字符间隔几个字符，这时候再去确认之后需要删除的索引就更麻烦了。

随后我又考虑检查非数字字符的方式，如果这个字符不是数字字符，再判断右边是否为数字字符，但是存在的问题和上面一样，并且这两种方式都需要考虑边界索引溢出的问题。

由于缺乏一定的算法基础，思考再三也没有想到合适的解题思路，偷摸打开题解看了一下，这题给的答案是使用栈来解决问题，理解了一下代码瞬间就通透了，这个问题就很好解决了。

当然解题不是目的，看完题解要去了解其中的背景知识，深入理解背后的原因，达到一通百通的目的。

代码（C语言）

char* clearDigits(char* s) {
    int top = 0; // 栈顶
    for(int i=0;i<strlen(s);i++){
        if(isdigit(s[i])){
            // 栈顶向前
            top--;
        }else{
            // 入栈
            s[top++]=s[i];
        }
    }
    // 在栈顶结束
    s[top]='\0';
    return s;
}