【Py/Java/C++三种语言详解】LeetCode每日一题240110【栈】LeetCode2696、删除子串后的字符串最小长度

2024-01-10 13:25:34

题目链接

LeetCode2696、删除子串后的字符串最小长度

题目描述

给你一个仅由 大写 英文字符组成的字符串 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 仅由大写英文字母组成

解题思路

非常典型的消消乐类型栈题,类似题目包括LeetCode20、有效的括号LeetCode1047、删除字符串中所有相邻重复项

维护一个栈,然后遍历s中的所有字符ch,考虑几种情况。当

  • ch"B"且栈顶元素为"A"的情况,删除这对"AB",即弹出栈顶的"A",当前"B"无需入栈
  • ch"D"且栈顶元素为"C"的情况,删除这对"CD",即弹出栈顶的"C",当前"D"无需入栈
  • 其余情况,没有出栈操作,元素直接入栈。

思考:如果可以构成的配对不止"AB""CD",还包括"EF""GH"、…、"YZ"等更多组配对,那么应该如何修改代码?

代码

Python

# 字符串消消乐类型题目:经典栈应用题
# 时间复杂度O(N),空间复杂度O(N)
# 相关题目:
# LeetCode20.有效的括号
# LeetCode1047. 删除字符串中的所有相邻重复项
class Solution:
    def minLength(self, s: str) -> int:
        # 初始化一个栈
        stack = list()
        # 遍历s中的每一个元素ch
        for ch in s:
            # ch是"B"且栈顶元素为"A"的情况,删除这对"AB"
            if ch == "B" and stack and stack[-1] == "A":
                    stack.pop()
            # ch是"D"且栈顶元素为"C"的情况,删除这对"cd"
            elif ch == "D" and stack and stack[-1] == "C":
                    stack.pop()
            # 其余情况,元素都需要入栈
            else:
                stack.append(ch)
        # 最终返回栈的长度,即为删除后所剩余的字符串长度
        return len(stack)

Java

public class Solution {
    public int minLength(String s) {
        Stack<Character> stack = new Stack<>();
        
        for (char ch : s.toCharArray()) {
            if (ch == 'B' && !stack.isEmpty() && stack.peek() == 'A') {
                stack.pop();
            } else if (ch == 'D' && !stack.isEmpty() && stack.peek() == 'C') {
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        
        return stack.size();
    }
}

C++

class Solution {
public:
    int minLength(string s) {
        stack<char> st;
        
        for (char ch : s) {
            if (ch == 'B' && !st.empty() && st.top() == 'A') {
                st.pop();
            } else if (ch == 'D' && !st.empty() && st.top() == 'C') {
                st.pop();
            } else {
                st.push(ch);
            }
        }
        
        return st.size();
    }
};

时空复杂度

时间复杂度:O(N)。仅需一次遍历字符串s

空间复杂度:O(M)。栈所占空间。


华为OD算法/大厂面试高频题算法练习冲刺训练

  • 华为OD算法/大厂面试高频题算法冲刺训练目前开始常态化报名!目前已服务100+同学成功上岸!

  • 课程讲师为全网50w+粉丝编程博主@吴师兄学算法 以及小红书头部编程博主@闭着眼睛学数理化

  • 每期人数维持在20人内,保证能够最大限度地满足到每一个同学的需求,达到和1v1同样的学习效果!

  • 60+天陪伴式学习,40+直播课时,300+动画图解视频,300+LeetCode经典题,200+华为OD真题/大厂真题,还有简历修改、模拟面试、专属HR对接将为你解锁

  • 可上全网独家的欧弟OJ系统练习华子OD、大厂真题

  • 可查看链接 大厂真题汇总 & OD真题汇总(持续更新)

  • 绿色聊天软件戳 od1336了解更多

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