【力扣】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)

简介: 【2月更文挑战第18天】2696. 删除子串后的字符串最小长度(模拟 栈 C++ Go实现栈)

题目链接

题意

给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作,在每一步操作中,你可以从 s 中删除 任一个 "AB" 或 "CD" 子字符串。
通过执行操作,删除所有 "AB" 和 "CD" 子串,返回可获得的最终字符串的 最小 可能长度。
注意,删除子串后,重新连接出的字符串可能会产生新的 "AB" 或 "CD" 子串。
提示:
$1 <= s.length <= 100$
s 仅由大写英文字母组成

思路1

题目里字符串$s$的长度只有100,可以选择暴力的将字符串$s$中的$AB/CD$去掉,直到字符串里没有$AB/CD$
时间复杂度是$O(n^2)$

代码1

go语言实现的代码,调用strings的方法来判断

  • strings.Contains(s,"AB") 判断字符串$s$里是否包含AB
  • strings.ReplaceAll(s,"AB","") 将字符串$s$的所有$AB$替换为空,也就是去除$AB$
    func minLength(s string) int {
         
      for strings.Contains(s,"AB") || strings.Contains(s,"CD") {
         
          s = strings.ReplaceAll(s,"AB","")
          s = strings.ReplaceAll(s,"CD","")
      }
      return len(s)
    }
    

    思路2

    用栈维护当前没有删除的字符,遍历字符串,
  • 如果当前遍历到的字符是B,并且栈顶元素为A,说明该字符入栈后可以构成$AB$的组合,需要将这两个字符都删除,即弹出栈顶元素
  • 同理,如果当前遍历到的字符是D,并且栈顶元素为C,说明该字符入栈后可以构成$CD$的组合,需要将这两个字符都删除,即弹出栈顶元素
  • 否则,将当前遍历到的字符入栈

最后栈的长度就是答案
时间复杂度是$O(n)$

代码2

c++代码,使用$STL$的栈$stack$

  • stack<char>stk 定义一个char类型的栈stk
  • stk.empty() 判断栈是否为空,为空时返回true
  • stk.top() 返回栈顶元素
  • stk.pop() 弹出栈顶元素
  • stk.push(ch) 将元素ch放入栈中
  • stk.size() 返回栈的大小
    class Solution {
         
    public:
      int minLength(string s) {
         
          stack<char>stk;
          for(int i=0;i<s.size();i++){
         
              char ch = s[i];
              if(!stk.empty()&&((ch=='B'&&stk.top()=='A')||(ch=='D'&&stk.top()=='C'))){
         
                  stk.pop();
              }else{
         
                  stk.push(ch);
              }
          }
          return stk.size();
      }
    };
    
    go代码,借助数组模拟栈
    因为栈是先进后出的结果,所以
  • 得到栈顶元素: 等价于得到数组的最后一个元素,即stk[len(stk) - 1]
  • 弹出栈顶元素:等价于删除数组的最后一个元素,即stk = stk[:len(stk) - 1]
  • 将元素ch放入栈中:等价于向数组中追加元素,即stk = append(stk,ch)
    func minLength(s string) int {
         
      var stk []rune
      for _,ch := range s {
         
          lasLen := len(stk) - 1
          if len(stk) > 0 && ( (ch=='B'&&stk[lasLen] == 'A') || (ch=='D'&&stk[lasLen] == 'C') ) {
         
              stk = stk[:lasLen]
          }else{
         
              stk  = append(stk,ch)
          }
      }
      return len(stk)
    }
    
目录
相关文章
|
1天前
|
索引
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
【力扣刷题】数组实现栈、后缀表达式(逆波兰表达式)求值、中缀表达式转换为后缀表达式(无括号&&有括号)
4 0
|
7天前
|
机器学习/深度学习 canal NoSQL
从C语言到C++_12(string相关OJ题)(leetcode力扣)
从C语言到C++_12(string相关OJ题)(leetcode力扣)
18 0
|
7天前
|
编译器 测试技术 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(下)
从C语言到C++_11(string类的常用函数)力扣58和415
7 0
|
7天前
|
存储 编译器 C语言
从C语言到C++_11(string类的常用函数)力扣58和415(中)
从C语言到C++_11(string类的常用函数)力扣58和415
11 0
|
7天前
|
存储 C语言 C++
从C语言到C++_11(string类的常用函数)力扣58和415(上)
从C语言到C++_11(string类的常用函数)力扣58和415
11 0
|
7天前
|
缓存 算法 C语言
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
数据结构与算法⑧(第三章_上)栈的概念和实现(力扣:20. 有效的括号)
5 0
|
13天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
8 0
|
13天前
|
存储 算法 安全
【刷题】 leetcode 面试题 01.06 字符串压缩
来看效果: 非常好!!!过啦!!!
30 5
【刷题】 leetcode 面试题 01.06 字符串压缩
|
13天前
leetcode代码记录(删除字符串中的所有相邻重复项
leetcode代码记录(删除字符串中的所有相邻重复项
14 0