一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
Offer多多
Salarytics
交友
Learn
Who's Hiring?
Visa Tracker
疫情动态
指尖新闻
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 619|回复: 1
收起左侧

[Leetcode] Wildcard Matching这题我用backtracking来写怎么就速度那么慢?

[复制链接] |只看干货 |leetcode, 刷题
我的人缘0

升级   86.9%


分享帖子到朋友圈
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (1078)
 
 
4% (55)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
额外写了个backtrack函数来写 而不是答案的那种two point的方法 感觉原理应该是一样的 但是我这个运行时间只超过了5%的人 还得再用cache来剪枝
是因为recursive stack的缘故么?但是这个不是应该只跟space有关么
[Java] 纯文本查看 复制代码
class Solution {
   HashSet<String> failed;

    public boolean isMatch(String s, String p) {
        failed = new HashSet<>();
        return backtrack(s, p, 0, 0);
    }

    private boolean backtrack(String s, String p, int si, int pi) {
        if (pi == p.length() && si == s.length()) return true;
        if (failed.contains(si + " " + pi)) {
            // System.out.println(si + " " + pi);
            return false;
        }
        boolean res = false;
        if (pi == p.length() || (si == s.length() && p.charAt(pi) != '*')) res = false;
        else if (p.charAt(pi) == '*') {
            if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') res = backtrack(s, p, si, pi + 1);
            else {
                for (int i = si; i <= s.length(); i++) {
                    if (backtrack(s, p, i, pi + 1)) {
                        res = true;
                        break;
                    }
                }
            }  
        } else {
            if (p.charAt(pi) != '?' && s.charAt(si) != p.charAt(pi)) res = false;
            else res = backtrack(s, p, si + 1, pi + 1);
        }
        if (!res) failed.add(si + " " + pi);
        return res;
    }
}

上一篇:做 Machine learning 相关的职位,大家都用什么语言刷题?
下一篇:刷多少hard/多快做完hard才算准备充分?
我的人缘0

升级   86.9%

 楼主| 刹那刹哪 2020-1-21 05:54:35 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   95% (1078)
 
 
4% (55)    👎
额下面不用回复了。。。看答案直接跳过了方法一 其实就是我这种 Recursion with memorisation
速度慢的原因是The first idea here is a recursion. That's a straightforward approach but quite time consuming because of huge recursion depth for long input strings.

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■拉群请前往同学同事飞友|拉群结伴版块,其他版块拉群,帖子会被自动删除
■论坛不能删帖,为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

Some icons made by Freepik from flaticon.com

快速回复 返回顶部 返回列表