思路
通过不断地检查是否含有"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();}
}