【LeetCode】双指针之比较含退格的字符串

我刚开始的思路是正着遍历,碰到#就删除两个(即#和它后面的字符),然后最终比较处理后的字符串。

但是这样问题是解决了,但是会超时,说明时间复杂度太高了,怎么回事呢?

是因为这样其实会有很多没必要处理的字符串被处理,比如两个字符串刚开始的字符就不一样但长度却很长,这样就会导致时间复杂度上升。所以我们是不是可以通过一边遍历一边比较的方法呢? 答案是可以的。 一边遍历怎么一边比较呢??

这时候我们可以想,如果是正着的话,当我们遍历到某个字符的时候,我们需要看这个字符后面是否有#、有多少个#,这样其实就不能算一边遍历一边比较了,嘶,#?

#表示删掉了之前输入的字符,那我们是不是可以认为从后往前遍历的时候,碰到#就可以跳过它前面的非#的字符了呢?

对! 就是这样,思路就有了,那么怎么跳呢?如果#前面还是#,#是不能跳过#的,所以我们需要记录#的数量,当碰到非#时,如果之前记录的#数量大于0,就可以跳过这个字符了~~

这样问题就解决啦

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function(s, t) {
    let i=s.length-1,j=t.length-1;
    let ss=0,st=0;
    while(i>=0 && j>=0){
        while(i>=0){
            if(s[i]==='#'){
                ss++;
            }
            if(s[i]!=='#' && ss===0){
                break;
            }
            if(s[i]!=='#' && ss!==0){
                ss--;
            }
            i--;
        }
        while(j>=0){
            if(t[j]==='#'){
                st++;
            }
            if(t[j]!=='#' && st===0){
                break;
            }
            if(t[j]!=='#' && st!==0){
                st--;
            }
            j--;
        }
        if(s[i]!==t[j]){
            return false;
        }
        else{
            i=i-1,j=j-1;
        }
    }
    if((i===0 && j!==0 && s[i]!=='#')||(i!==0 && j===0 && t[j]!=='#')){
        return false
    }
    return true;
};
上一篇:实战:如何掌握Oracle和业务IO知识


下一篇:前端和数据库时间差8小时?