前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >双指针之比较含退格的字符串

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

作者头像
xinxin-l
发布2022-03-30 16:09:37
3450
发布2022-03-30 16:09:37
举报

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

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

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

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

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

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

这样问题就解决啦

代码语言:javascript
复制
/**
 * @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;
};
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2022-02-15,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 表示删掉了之前输入的字符,那我们是不是可以认为从后往前遍历的时候,碰到#就可以跳过它前面的非#的字符了呢?
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档