844 Backspace String Compare

Leetcode

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: s = "ab#c", t = "ad#c"  
Output: true  
Explanation: Both s and t become "ac".

Example 2:

Input: s = "ab##", t = "c#d#"
Output: true
Explanation: Both s and t become "".

Example 3:

Input: s = "a#c", t = "b"
Output: false
Explanation: s becomes "c" while t becomes "b".

转化成字符串比较。使用栈，遇到字母压入，遇到 # 号弹出。时间复杂度 o(n) ，空间复杂度 o(n)

    public boolean backspaceCompare(String s, String t) {
        return getStr(s).equals(getStr(t));
    }
    
    public String getStr(String s){
        Deque<Character> stack = new LinkedList<>();
        for(int i=0;i<s.length();++i){
            char c=s.charAt(i);
            if(c=='#'){
                if(stack.size()>0) stack.pop();
            } else {
                stack.push(c);
            }
        }
        StringBuilder sb=new StringBuilder(stack.size());
        while(stack.size()>0){
            sb.append(stack.removeLast());
        }
        return sb.toString();
    }

时间复杂度 o(n)，空间复杂度 o(1) 的方法：从后往前遍历，遇到 # 就计数，不断往左移动到头或者到该删除的字母都删除了，得到的字母就是最终结果的右边的字母，不断重复，从最终结果的右边依次比较。

public boolean backspaceCompare(String s, String t) {
    int i1=0, i2=0;
    char c1=' ',c2=' ';
    int count1=0, count2=0;
    while(true){
        while(count1>0 && i1>=0){

            c1=s.charAt(i1--);
            if(c1=='#') count1++;
        }
        while(count2>0 && i2>0){
            
            c2=t.charAt(i2);
            i2--;
            if(c2=='#') count2++;
        }
        if(c1!=c2) return false;
        if(i1==-1 && i2==-1) return true;
        if(i1==-1 || i1==-1){
            while(i1>=0){
                if(s.charAt(i1--)!='#') return false;
            }
            while(i2>=0){
                if(t.charAt(i2--)!='#') return false;
            }
            return true;
        }
    }
}