比较两个包含退格的字符串是否相等

本是古典何须时尚 2022-12-16 06:43 203阅读 0赞

\#号表示退格，如果字符串中包含\#号，则\#号及前一个字符为空，如字符串1：adb\#ch，为abch；字符串2：asj\#\#f，为af。  
示例：  
字符串S：ab\#c；  
字符串T：ad\#c；  
输出结果：true

思路分析：  
①从后往前倒序比较；  
②遇到\#号，则跳过，且\#号后一个字符也跳过；  
③比较跳过\#号及其后面字符后的字符串是否相等。

代码实现：

public boolean backspaceCompare(String S, String T) {
    
            StringBuilder ss = new StringBuilder();//新建一个空字符串ss
            StringBuilder tt = new StringBuilder();//新建一个空字符串tt
            
            int count = 0;//新建一个变量count用来计算#号数量，count初始值为0
    
            //如果字符串S和T之间有一个是空字符串，则这两个字符串不相等
            if(S == null || T == null){
                return false;
            }
    
            //从后往前遍历字符串S
            for(int i=S.length()-1;i>=0;i--){
    
                char s = S.charAt(i);//新建变量s,s的值为字符串中当前字符
                //判断当前字符是不是#号
                if(s == '#'){//当前字符是#号
                    count++;//#号总数量+1，跳过当前字符
                    continue;//跳出本次循环
                }
    
                //判断count是否大于0
                if(count > 0){//count>0
                    count --;//#号总数量-1，跳过当前字符
                    continue;//跳出本次循环
                }else{//count=0，无需继续跳过当前字符
                   ss.append(s);//将当前字符放入字符串ss中
                }
            }
    
            //用相同的方法倒叙遍历字符串T
            count = 0;
    
            for(int j=T.length()-1;j>=0;j--){
                char t = T.charAt(j);
                if(t == '#'){
                    count++;
                    continue;
                }else if(count > 0){
                    count --;
                    continue;
                }else{
                    tt.append(t);
                }
            }
    
            //比较遍历后得到的字符串ss和tt是否相等
            if(ss.toString().equals(tt.toString())){
                return true;
            }else{
                return false;
            }
        }