leetcode844 比较含退格的字符串

双指针写法(不好想到)
m,n分别代表两个字符串长度
空间复杂度o(1)优秀
空间复杂度o(m+n)优秀 需要遍历两字符串各一次

var backspaceCompare = function(S, T) {
    let i = S.length - 1,
        j = T.length - 1,
        skipS = 0,
        skipT = 0;
    // 大循环
    while(i >= 0 || j >= 0){
        // S 循环
        while(i >= 0){
            if(S[i] === '#'){
                skipS++;
                i--;
            }else if(skipS > 0){
                skipS--;
                i--;
            }else break;
        }
        // T 循环
        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;
};

常规方法：用栈先进行处理，去掉字符串中的#和该退格的字符，在比较两个字符串是否相同
空间复杂度o(m+n)
时间复杂度o(m+n) 需要遍历两字符串各一次

var backspaceCompare = function(S, T) {
    return dealStr(S) === dealStr(T)
};

function dealStr(str){
    let result = []
    for(let i = 0; i < str.length; i++){
        if(str[i] === '#'){
            result.pop()
        }else{
            result.push(str[i])
        }
    }
    return result.join("")
}