每日一题——LeetCode844

方法一 暴力法：

对两个字符串分别从头到尾遍历一遍，遇到#就删除#和它之前的那个字符，如果遇到#在字符串的第一位则只用删除#，最后将删除后的不含#的两个字符串进行比较是否一样

var backspaceCompare = function(s, t) {
  for(var i=0;i<s.length;i++){
        if(s[i]==='#'){
            if(i===0){
                s=s.slice(1);
                i--;
            }else{
                s=s.slice(0,i-1)+s.slice(i+1);
                i-=2 ;
            }
            
        }
    }

    for(var i=0;i<t.length;i++){
        if(t[i]==='#'){
            if(i===0){
                t=t.slice(1);
                i--;
            }else{
                t=t.slice(0,i-1)+t.slice(i+1);
                i-=2;
            }
        }
    }
    return s===t;
};

消耗时间和内存：

方法二 双指针法：

两个指针分别指向s和t的尾部，从尾部开始每一位进行比较， 碰到#时用skip++代表要跳过一位进行比较，变相相当于删除了#之前那一个字符。若对比过程出现 S, T 当前字符不匹配，则遍历结束，返回 false，若 S，T 都遍历结束，且都能一一匹配，则返回 true。

var backspaceCompare = function(S, T) {
    let i = S.length - 1,
        j = T.length - 1,
        skipS = 0,
        skipT = 0;

    while(i >= 0 || j >= 0){

        while(i >= 0){
            if(S[i] === '#'){
                skipS++;
                i--;
            }else if(skipS > 0){
                skipS--;
                i--;
            }else break;
        }

        while(j >= 0){
            if(T[j] === '#'){
                skipT++;
                j--;
            }else if(skipT > 0){
                skipT--;
                j--;
            }else break;
        }
        if(S[i] !== T[j]) return false;
        i--;
        j--;
    }
    return true;
}

消耗时间和内存：?

?

方法三 栈：

和方法一类似，从前往后遍历，遇到字符先push进数组，遇到#就把数组最后一个元素移出，最后把两个数组转为字符串比较是否相同

var backspaceCompare = function(S, T) {
   var a=[],b=[]
   for(var i=0;i<S.length;i++){
    if(S[i]==='#'){
        a.pop()
    }else{
        a.push(S[i])
    }
   }

   for(var i=0;i<T.length;i++){
    if(T[i]==='#'){
        b.pop()
    }else{
        b.push(T[i])
    }
   }

   return a.join('')===b.join('')
}

消耗时间和内存：?

总体来说，三种方法耗时差不多