【每日一题】删除子串后的字符串最小长度

2024-01-10 07:22:35

Tag

【栈】【字符串】【2024-01-10】


题目来源

2696. 删除子串后的字符串最小长度


解题思路

方法一:栈

思路

按照题目要求需要移除字符串中的 “AB” 和 “CD” 子字符串,并且移除这两种字符之后可能还会出现这样的字符,于是考虑使用栈这种基本的数据结构。

当栈顶两个元素分别为 “AB” 或 “CD” 时,可以通过出栈来模拟移除操作。这样,后续的判断过程就是建立在已经删除元素的栈之上了。遍历完之后,返回栈的长度。

算法

class Solution {  
private:
    unordered_map<char, char> pairs;
public:
    int minLength(string s) {
        pairs['B'] = 'A';
        pairs['D'] = 'C';
        int ans = 0;
        stack<char> stk;
        
        for (int i = 0; i < s.size(); ++i) {
            if (stk.empty()) {
                stk.push(s[i]);
                continue;
            }
            char c = stk.top();
            if (c == pairs[s[i]]) {
                stk.pop();
            }
            else {
                stk.push(s[i]);
            }  
        }
        return stk.size();
    }
};

复杂度分析

时间复杂度: O ( n ) O(n) O(n) n n n 为字符串 s 的长度。

空间复杂度: O ( 1 ) O(1) O(1)


写在最后

如果您发现文章有任何错误或者对文章有任何疑问,欢迎私信博主或者在评论区指出 💬💬💬。

如果大家有更优的时间、空间复杂度的方法,欢迎评论区交流。

最后,感谢您的阅读,如果有所收获的话可以给我点一个 👍 哦。

文章来源:https://blog.csdn.net/weixin_54383080/article/details/135492663
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。