day-05 删除子串后的字符串最小长度

思路
通过不断地检查是否含有"AB"或"CD"，如果有则将其从字符串中删除，直到"AB"或"CD"都不存在时，返回字符串的长度

解题方法
//检测是否有"AB"
for(int i=0;i<len-1;i++){
if(s.charAt(i)‘A’&&s.charAt(i+1)‘B’){
s=s.substring(0,i)+s.substring(i+2);
flag1=false;
len=s.length();
}
}

//检测是否有"CD"
for(int i=0;i<len-1;i++){
if(s.charAt(i)‘C’&&s.charAt(i+1)‘D’){
s=s.substring(0,i)+s.substring(i+2);
flag1=false;
len=s.length();
}
}

“AB” "CD"都不存在，则返回字符串长度
使用while(true)进行不断循环,直到得到最小字符串

时间复杂度: O(n)

空间复杂度: O(1)
Code

    public int minLength(String s) {
        int len=s.length();;
        boolean flag1,flag2;
        while(true){
            flag1=true;
            flag2=true;
            //检测是否有"AB"
            for(int i=0;i<len-1;i++){
                if(s.charAt(i)=='A'&&s.charAt(i+1)=='B'){
                    s=s.substring(0,i)+s.substring(i+2);
                    flag1=false;
                    len=s.length();
                }
            }
            //检测是否有"CD"
            for(int i=0;i<len-1;i++){
                if(s.charAt(i)=='C'&&s.charAt(i+1)=='D'){
                    s=s.substring(0,i)+s.substring(i+2);
                    flag1=false;
                    len=s.length();
                }
            }
            //"AB" "CD"都不存在，则返回字符串长度
            if(flag1==true&&flag2==true) break;
        }
        return s.length();
    }

官方答案：

class Solution {
    public int minLength(String s) {
        List<Character> stack = new ArrayList<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            stack.add(c);
            int m = stack.size();
            if (m >= 2 &&
                (stack.get(m - 2) == 'A' && stack.get(m - 1) == 'B' ||
                stack.get(m - 2) == 'C' && stack.get(m - 1) == 'D')) {
                stack.remove(m - 1);
                stack.remove(m - 2);
            }
        }
        return stack.size();
    }
}