一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3605|回复: 16
收起左侧

[算法题] [Leetcode]花半年解决Wildcard Matching 而且还是用Python另附完整Java

[复制链接] |试试Instant~ |关注本帖
Linzertorte 发表于 2014-7-10 13:35:37 | 显示全部楼层 |阅读模式

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 Linzertorte 于 2014-7-10 19:24 编辑

找工作的时候刷leetcode,主要用C++刷了140题。但是Wildcard matching死活过不了。
类似的regular expression matching用回溯过了。
然后今天受到一个启发用Non-deterministic automata来做。一个bit_vector表示当前状态。
然后这个NFA也很好构造。如果对应位置有个*,说明有一个自环。如果是字母或者?,有一个走向下一状态的边。
代码倒是好写。

首先这题如果有连续有*.那么只保留一个即可。
这个复杂度为O(m*n) m 是len(s), n是len(p)



然后发就Time limited exceed在之前C++就通不过那个长长的"aaaaaaaaaaaaaaaaaaaaaaaaa..."上。然后就以为是因为他有许多"aaaa",然后pattern是一个aaaa*所以过了不。
然后就想到一个优化。把pattern分解成三个部分 第一部分与第三部分都没有*
left,middle, right
比如pattern=abc*daf?*dsaf*?df
left=abc
middle = *daf?*dsaf*
right = ?df
1.jpg


我们定义match_from(i,s,p)  即一个不含*,可能含有?的pattern p可以match s[i..i+len(pattern)-1]
然后还是超时。

不过这个将pattern分成三部分的想法又给了我一个启发。

其实我们完全可以将这个pattern按照*来split.得到的chunks都不含有*

然后这题要求exact match
所以第一个chunk和最后一个chunk必须与s的开头和结尾match



剩下的就是中间的chunks,还有那个去头去尾的s,如果称去头去尾的s为s'

我们接下来的match就可以采取信心的策略。

Untitled drawing.jpg



上面为s',下面就是chunks.
没有arrow指向的s'中字母我们一律用*来match

每个chunk我们只需要尽可能靠左去match.这个不会影响结果。而且这个性质很容易证明。

开始让begin=0
然后发现   match_from(begin,'aaa',s') ==True  
这样aaa match就match上了。
我们让begin += len('aaa')
begin现在是3.
即从3开始match第二个chunk bbc
直到begin==11的时候match_from(begin,'bbc',s')==True
我们又完成了第二个chunk的match..
..如此如此so on and so forth.
然后下面是代码

2.jpg


这一大段主要是用来对s进行掐头去尾。。许多corner case


3.jpg

最后的几行就是小贪心一下。

最后的最后是我的提交记录。真的半年啦
5.jpg





评分

4

查看全部评分

 楼主| Linzertorte 发表于 2014-7-10 19:41:34 | 显示全部楼层
回复 支持 1 反对 0

使用道具 举报

 楼主| Linzertorte 发表于 2014-7-10 19:22:30 | 显示全部楼层
这里附上另外整理的Java代码。
wildcard.jpg
回复 支持 0 反对 1

使用道具 举报

ralf 发表于 2014-7-10 21:54:15 | 显示全部楼层
这题G onsite考到了,我当时写的是:

    bool isMatch(const char *s, const char *p)
    {
        const char* star_pos = 0;
        const char* s_pos = 0;
        
        while(*s != '\0')
        {
           if(*s == *p || *p == '?') //一对一的match
           {
               s++;
               p++;
               continue;
           }
           if(*p == '*') //很多'*'连在一起和一个'*'效果是一样的
           {
               star_pos = p;
               p++;
               s_pos = s;
               continue;
           }
           if(star_pos != 0)
           {
               s = s_pos++; //s_pos的作用是如果s和p在第一个if里不能匹配到底(即p到底s还没到底),s可以重新回到s_pos
                            //s_pos++后重新开始匹配相当于'*'又多消灭s中的一个字符
               p = star_pos+1; //p重新回到star_pos+1
               continue;
           }
           return false; //如果上面三个if都进不去,s又还没到头,那么匹配失败
        }
        while(*p == '*') p++; //忽略剩下的'*'
        return *p == '\0';
    }
回复 支持 1 反对 0

使用道具 举报

pyemma 发表于 2014-7-10 20:57:33 | 显示全部楼层
当初用java写的,调了一个晚上才过了,一开始用DP超时,后来改用贪心+KMP才过了
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-7-10 22:10:35 | 显示全部楼层
ralf 发表于 2014-7-10 21:54
这题G onsite考到了,我当时写的是:

    bool isMatch(const char *s, const char *p)

幸亏我G onsite没面这题。要不然我就挂了。
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-7-11 02:38:20 | 显示全部楼层
pyemma 发表于 2014-7-10 20:57
当初用java写的,调了一个晚上才过了,一开始用DP超时,后来改用贪心+KMP才过了

KMP点赞。
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-7-11 11:24:08 | 显示全部楼层

理解了KMP,写带?的KMP就很简单了
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2014-7-11 12:37:59 | 显示全部楼层
pyemma 发表于 2014-7-11 11:24
理解了KMP,写带?的KMP就很简单了

这倒也是。计算next指针的时候比如p==?或者p==s[j]都算是匹配成功。
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-7-11 18:06:07 | 显示全部楼层
Linzertorte 发表于 2014-7-11 12:37
这倒也是。计算next指针的时候比如p==?或者p==s[j]都算是匹配成功。

是的
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-7-11 18:06:42 | 显示全部楼层
Linzertorte 发表于 2014-7-11 12:37
这倒也是。计算next指针的时候比如p==?或者p==s[j]都算是匹配成功。

不过我还是被python的超短code惊异到了,我用Java足足写了100行!
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-22 11:01:45 | 显示全部楼层
这题是LC最难过的一道了 谢谢lz分享!
回复 支持 反对

使用道具 举报

austurela 发表于 2014-10-22 11:27:04 | 显示全部楼层
仔细看了,真是相当nb的解法!
回复 支持 反对

使用道具 举报

AndyLiu0429 发表于 2014-12-17 22:02:09 | 显示全部楼层
本帖最后由 AndyLiu0429 于 2014-12-17 22:03 编辑

当时做regular 匹配的时候TLE,我直接把pattern 缩减了下。。举例,'aaa*' -> 'aa*'(匹配的字符串是一样的,后者表达能力更强。。)
做这道题参考了Yu 的思路,记录*的思路实在太漂亮了。
AC过了,我的代码:
    def isMatch(self, s, p):
        len_s, len_p = len(s), len(p)
        pPointer=sPointer=0
        star = -1
        while sPointer < len_s:
            if pPointer >= len_p:
                if star != -1:
                    sPointer, pPointer = star
                    sPointer +=1
                    continue
                else:
                    return False
            if p[pPointer] == "?" or p[pPointer]==s[sPointer]:
                pPointer+=1
                sPointer+=1
            elif p[pPointer] == '*':
                star = (sPointer,pPointer)
                pPointer+=1
            else:
                if star != -1:
                    sPointer, pPointer = star
                    sPointer +=1
                else:
                    return False

        if pPointer < len_p:
            while pPointer < len_p and p[pPointer]=='*':
                pPointer+=1

        return True if pPointer == len_p else False

回复 支持 反对

使用道具 举报

miss_snow 发表于 2014-12-18 07:56:28 | 显示全部楼层
怎么感觉像是AC自动机?
回复 支持 反对

使用道具 举报

 楼主| Linzertorte 发表于 2015-1-31 00:38:54 | 显示全部楼层
austurela 发表于 2014-10-22 11:01
这题是LC最难过的一道了 谢谢lz分享!

一般一般。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 18:21

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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