【LeetCode2696】删除子串后的字符串最小长度-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode2696】删除子串后的字符串最小长度。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

1、题目描述

【题目链接】
标签：栈 、字符串、模拟
难度：简单
给你一个仅由大写英文字符组成的字符串 s 。
你可以对此字符串执行一些操作，在每一步操作中，你可以从 s 中删除任一个 “AB” 或 “CD” 子字符串。
通过执行操作，删除所有 “AB” 和 “CD” 子串，返回可获得的最终字符串的最小可能长度。
注意，删除子串后，重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。

示例 1：
输入：s = “ABFCACDB”
输出：2
解释：你可以执行下述操作：

从 “ABFCACDB” 中删除子串 “AB”，得到 s = “FCACDB” 。
从 “FCACDB” 中删除子串 “CD”，得到 s = “FCAB” 。
从 “FCAB” 中删除子串 “AB”，得到 s = “FC” 。
最终字符串的长度为 2 。
可以证明 2 是可获得的最小长度。

示例 2：
输入：s = “ACBBD”
输出：5
解释：无法执行操作，字符串长度不变。

提示：
1 <= s.length <= 100
s 仅由大写英文字母组成

2、基本思路

这是一道简单的字符串处理的题目，可以用栈模型上述的删除的过程即可，值得注意的是，删除子串后，重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。

下面是利用栈对示例 1 模拟的过程：文章来源地址https://www.toymoban.com/news/detail-796294.html

初始化栈空；
栈空，A入栈；
当前元素B，与栈顶元素A，构成子串AB，A出栈；
栈空，F入栈；
当前元素C，栈顶元素F，构不成子串，C入栈；
当前元素A，栈顶元素C，构不成子串，A入栈；
当前元素C，栈顶元素A，构不成子串，C入栈；
当前元素D，栈顶元素C，构成子串CD，C出栈；
当前元素B，栈顶元素A，构成子串AB，A出栈；
字符串元素遍历完毕，栈中元素的长度即为答案；

3、代码实现


int minLength(string s) {
    stack<char> st;
    for(int i = 0;i<s.length();++i)
    {
        char c = s[i];
        if(st.empty())
            st.push(c);
        else
        {
            if(c=='D'&&st.top()=='C')
                st.pop();
            else if(c=='B'&&st.top()=='A')
                st.pop();
            else
                st.push(c);
        }
    }
    return st.size();    
}