// @Title: 比较含退格的字符串 (Backspace String Compare)
// @Author: qisiii
// @Date: 2024-09-06 18:21:54
// @Runtime: 0 ms
// @Memory: 40.6 MB
// @comment: 双指针用来判断真正的字符串是啥，但还是重新创建了字符串，因此时间复杂度O(2n)=O(n)，空间复杂度O(n)
// @flag: RED
class Solution {
    public boolean backspaceCompare(String s, String t) {
        return doSolution(s).equals(doSolution(t));
    }
    public String doSolution(String s){
        int start=0,cur=0;
        char[] arr=s.toCharArray();
        while(cur<s.length()){
            if(arr[cur]=='#'){
                if(start>0){
                    start--;
                }
                cur++;
                continue;
            }
            arr[start++]=arr[cur];
            cur++;
        }
        StringBuilder build=new StringBuilder();
        for(int i=0;i<start;i++){
            build.append(arr[i]);
        }
        return build.toString();
    }
}

// @Title: 比较含退格的字符串 (Backspace String Compare)
// @Author: qisiii
// @Date: 2024-09-06 19:34:00
// @Runtime: 0 ms
// @Memory: 40.5 MB
// @comment: 倒着遍历，比较每一轮中要保留的字符串
// @flag: GREEN
class Solution {
    public boolean backspaceCompare(String s, String t) {
       int i=s.length()-1,j=t.length()-1;
       int delI=0,delJ=0;
       while(i>=0||j>=0){
       while(i>=0){
        if(s.charAt(i)=='#'){
            delI++;
        }else if(delI>0){
            delI--;
        }else{
            break;
        }
        i--;
       }
       while(j>=0){
        if(t.charAt(j)=='#'){
            delJ++;
        }else if(delJ>0){
            delJ--;
        }else{
            break;
        }
        j--;
       }
       if(i>=0&&j>=0){
            if(s.charAt(i)!=t.charAt(j)){
                return false;
            }
        
       }else{
            if(i>=0||j>=0){
                return false;
            }
       }
       i--;j--;
       }
       return true;
    }
}