北京网站制作网站优化,阿里云wordpress数据库备份,网站首页标题字数,素材图片高清【LetMeFly】2696.删除子串后的字符串最小长度#xff1a;栈
力扣题目链接#xff1a;https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作#xff0c;在每一步操…【LetMeFly】2696.删除子串后的字符串最小长度栈
力扣题目链接https://leetcode.cn/problems/minimum-string-length-after-removing-substrings/
给你一个仅由 大写 英文字符组成的字符串 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 100s 仅由大写英文字母组成
方法一栈
使用一个栈存放字符串剩下的元素遍历字符串
如果当前字符是B并且栈顶元素是A则A出栈否则如果当前字符是D并且栈顶元素是C则C出栈否则当前字符入栈
最终返回栈中元素的个数即可。
时间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))空间复杂度 O ( l e n ( s ) ) O(len(s)) O(len(s))
AC代码
C
class Solution {
public:int minLength(string s) {stackchar st;for (char c : s) {if (c B st.size() st.top() A) {st.pop();}else if (c D st.size() st.top() C) {st.pop();}else {st.push(c);}}return st.size();}
};Python
class Solution:def minLength(self, s: str) - int:st []for c in s:if (c B and st and st[-1] A) or (c D and st and st[-1] C):st.pop()else:st.append(c)return len(st)同步发文于CSDN原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/135511159
