# 844. Backspace String Compare

###### tags: `leetcode`,`easy`

>ref: https://leetcode.com/problems/backspace-string-compare/
>
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.


Constraints:

* 1 <= s.length, t.length <= 200
* s and t only contain lowercase letters and '#' characters.

### spatail O(N)
>1. stack存放抽取,最後比較 time:O(N) loop all spatial O(N) 存放字串

    public boolean backspaceCompare(String s, String t) {
        
        
        Stack<Integer> s1=new Stack<>();
        Stack<Integer> t1=new Stack<>();
        
        for(int i=0; i< s.length();i++){
            if(s.charAt(i)=='#' && !s1.isEmpty()){
                s1.pop();
            }else if(s.charAt(i)!='#'){
                s1.add(s.charAt(i)-'a');
            }
        }
        
        for(int i=0; i< t.length();i++){
            if(t.charAt(i)=='#'&& !t1.isEmpty()){
                t1.pop();
            }else if(t.charAt(i)!='#'){
                t1.add(t.charAt(i)-'a');
            }
        }
        
        if(s1.size()!=t1.size()){
            return false;
        }
        
        while(!s1.isEmpty() && !t1.isEmpty()){
            if(s1.pop() != t1.pop()){
                return false;
            }
        }
        
        return true;
    }

### spatail O(1)
>1. 從尾端比較最後存在字串字元

    public boolean backspaceCompare(String s, String t) {
        
        int idx_s=s.length()-1;
        int idx_t=t.length()-1;
        
        while(idx_s>=0 || idx_t>=0){
            idx_s=queryNonBackSpace(s,idx_s);
            idx_t=queryNonBackSpace(t,idx_t); 
            
            if( (idx_s<0 && idx_t>=0) ||  (idx_t<0 && idx_s>=0)  || ((idx_t>=0 && idx_s>=0) && s.charAt(idx_s)!=t.charAt(idx_t))){
                return false;
            }
            idx_s--;
            idx_t--;
        }
            return true;
    }
    
    
    private int queryNonBackSpace(String str,int idx){
        
        if(idx<0) return -1;
        
        //start from idx to front, find the non back spaced affected char idx
        int backspace_c=0;
        
        do{
            if(str.charAt(idx)=='#'){
                backspace_c++;
            }else{
                if(backspace_c>0){
                    backspace_c--;
                }else{
                    return idx;
                }
            }
            idx--;
        }while(backspace_c>=0 && idx>=0);
        
        return -1;

    }