题目链接

题意

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