leetcode上wild match - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

leetcode上wild match

leetcode上wild match# JobHunting - 待字闺中

g*e2012-04-08 07:04

1 楼

class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(*s=='\0'){
if(*p=='\0')
return true;
else if(*p=='*')
return isMatch(s, p+1);
else
return false;
}
else{
if(*p=='\0')
return false;
else if(*p=='?' || *p==*s)
return isMatch(s+1,p+1);
else if(*p=='*')
return isMatch(s+1,p) || isMatch(s,p+1);
else
return false;
}
}
};
这是我的代码，通过了small judge, 但是large judge的时候exceeded time limit。
大家帮忙看看哪里可以优化？谢谢啦
另外 '\0'这个char是不是就等于0？可以写成（*s==0）来判断吗？

p*22012-04-08 07:04

2 楼

这道题我还没做过呢。明天有时间做一下

【在 g*********e 的大作中提到】

: class Solution {
: public:
: bool isMatch(const char *s, const char *p) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: if(*s=='\0'){
: if(*p=='\0')
: return true;
: else if(*p=='*')
: return isMatch(s, p+1);

g*e2012-04-08 07:04

3 楼

刚出的还有俩道找路径数的题

【在 p*****2 的大作中提到】

:
: 这道题我还没做过呢。明天有时间做一下

p*22012-04-08 07:04

4 楼

上边的题你都做了？

【在 g*********e 的大作中提到】

:
: 刚出的还有俩道找路径数的题

g*e2012-04-08 07:04

5 楼

熟悉的做了，数独什么都没做

【在 p*****2 的大作中提到】

:
: 上边的题你都做了？

l*82012-04-08 07:04

6 楼

问题在这句：
else if(*p=='*')
return isMatch(s+1,p) || isMatch(s,p+1);

【在 g*********e 的大作中提到】

l*82012-04-08 07:04

7 楼

有多个 * 的时候，程序时间就指数级增长了。
可以考虑如下方案：
当遇到 * 的时候，找出该 * 后面紧接的非*字符，记其为一个字符串u, 然后在s中
寻找字符串u，
比如：
s = "daaaabcdxdxyz"
p = "d*abc*xyz"
当碰到第一个*的时候，在"aaaabcdxdxyz"找"abc"，
找到之后，接着匹配"dxdxyz"和"*xyz"

【在 l*********8 的大作中提到】

: 问题在这句：
: else if(*p=='*')
: return isMatch(s+1,p) || isMatch(s,p+1);

g*r2012-04-08 07:04

8 楼

I solve the problem using DP.
ismatch[i][j] means pattern[j...] can match str[i...]
but the last largest case is a 30000 size str and 30000 size pattern.
I pass that case using branch cut: exclude stars pattern must be less or
equal than str.
Maybe there exists more efficient algorithm.

l*a2012-04-08 07:04

9 楼

when *s=='\0'
*p=='.' && *(p+1)=='*'
what will u return?

【在 g*********e 的大作中提到】

l*82012-04-08 07:04

10 楼

so it probably requires a lot of extra memory? Say, 30000*30000?

【在 g**********r 的大作中提到】

: I solve the problem using DP.
: ismatch[i][j] means pattern[j...] can match str[i...]
: but the last largest case is a 30000 size str and 30000 size pattern.
: I pass that case using branch cut: exclude stars pattern must be less or
: equal than str.
: Maybe there exists more efficient algorithm.

l*82012-04-08 07:04

11 楼

贴一下我的程序，通过了leetcode judge.
感觉还是有些繁琐.
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(!s || !p)
return false;
if(p[0] == '\0' && s[0] != '\0')
return false;
const char * star = NULL;
const char * nextStar = NULL;
if (p[0] == '*') {
star = p;
p++;
}
while (1) {
nextStar = strchr(p, '*');
if (nextStar != NULL) {
if (star == NULL) { // no previous '*'
if (compareNoStarStringN(s, p, nextStar - p) == false)

return false;
s += (nextStar - p);
} else { // has previous '*'
const char * next_s = findNoStarSubStringN(s, p,
nextStar - p);
if (next_s == NULL)
return false;
s = next_s + (nextStar - p);
}
} else { // no '*' in the rest of the string
int pLength = strlen(p);
int sLength = strlen(s);
if (star == NULL) {
if (pLength != sLength)
return false;
return compareNoStarStringN(s, p, pLength);
} else {
if (sLength < pLength)
return false;
return compareNoStarStringN(s+sLength-pLength, p,
pLength);
}

}
star = nextStar;
p = star + 1;
}
}
private:
const char * findNoStarSubStringN(const char * str, const char *target,
int targetLength)
{
int n = strlen(str);
while(n>=targetLength) {
if (compareNoStarStringN(str, target, targetLength))
return str;
str++;
n--;
}
return NULL;
}
bool compareNoStarStringN(const char * s, const char * p, int n)
{
if (strlen(s) < n)
return false;
while( n>0 && ( *s == *p || *p == '?' ) ) {
s++;
p++;
n--;
}
return n==0;
}
};

l*a2012-04-08 07:04

12 楼

你有信心45分钟内把这些全完成？而且还给面试官讲清楚？

【在 l*********8 的大作中提到】

: 贴一下我的程序，通过了leetcode judge.
: 感觉还是有些繁琐.
: class Solution {
: public:
: bool isMatch(const char *s, const char *p) {
: // Start typing your C/C++ solution below
: // DO NOT write int main() function
: if(!s || !p)
: return false;
: if(p[0] == '\0' && s[0] != '\0')

l*82012-04-08 07:04

13 楼

肯定完成不了....

【在 l*****a 的大作中提到】

: 你有信心45分钟内把这些全完成？而且还给面试官讲清楚？

l*82012-04-08 07:04

14 楼

I modified the program.
Now the major function should be simple enough (although the whole
program is not that short).
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if(!s || !p )
return false;
const char * nextStar = strchr(p, '*');
if ( !nextStar)
return strCmp(s, p);
if (!strCmpN(s, p, nextStar-p) )
return false;
do {
s += nextStar-p;
p = nextStar + 1;
nextStar = strchr(p, '*');
if (!nextStar)
return strCmp(max(s, s+strlen(s)-strlen(p)), p);
s = strStrN(s, p, nextStar - p);
} while (s);
return false;
}
// -------------------------------------------
private:
// Find substring of str that match length-n pattern p;
// Consider '?' but not '*'
const char * strStrN(const char * str, const char *p, int n)
{
const char * strEnd = str + strlen(str) - n + 1;
while(str < strEnd && !strCmpN(str, p, n))
str++;
return str < strEnd ? str : NULL;
}
// compare if first n chars of str match length-n pattern target;
// Consider '?' but not '*'
bool strCmpN(const char * s, const char * p, int n)
{
const char * pEnd = p+n;
while( p!=pEnd && *s && ( *s == *p || *p == '?' ) ) {
s++;
p++;
}
return p==pEnd;
}
bool strCmp(const char * s, const char * p)
{
int n = strlen(p);
if (strlen(s)!=n)
return false;
return(strCmpN(s, p, n));
}
};

p*22012-04-08 07:04

15 楼

我今天做做这个。基本的程序很好写，也适合面试写。但是确实time out.得想办法优
化。

p*22012-04-08 07:04

16 楼

这题leetcode没有给标准解吗？

l*a2012-04-08 07:04

17 楼

给了，很清晰易懂啊
不明白楼上为什么不参考

【在 p*****2 的大作中提到】

: 这题leetcode没有给标准解吗？

l*82012-04-08 07:04

18 楼

but it seems to be a different question....
the meaning of * is different.

【在 l*****a 的大作中提到】

: 给了，很清晰易懂啊
: 不明白楼上为什么不参考

p*22012-04-08 07:04

19 楼

能给个link吗？

【在 l*****a 的大作中提到】

: 给了，很清晰易懂啊
: 不明白楼上为什么不参考

l*a2012-04-08 07:04

20 楼

http://www.leetcode.com/2011/09/regular-expression-matching.htm

【在 p*****2 的大作中提到】

:
: 能给个link吗？

i*e2012-04-08 07:04

21 楼

在网站上那个是 regex match，不是 wildcard match。
wildcard match 递归的 complexity 是 exponential 的。
你必须写个非递归的 O(m*n)，才能通过 large input.

【在 p*****2 的大作中提到】

:
: 能给个link吗？

l*a2012-04-08 07:04

22 楼

oh???
let me see see

【在 l*********8 的大作中提到】

: but it seems to be a different question....
: the meaning of * is different.

p*22012-04-08 07:04

23 楼

m*n就是dp了吧？

【在 i**********e 的大作中提到】

: 在网站上那个是 regex match，不是 wildcard match。
: wildcard match 递归的 complexity 是 exponential 的。
: 你必须写个非递归的 O(m*n)，才能通过 large input.

i*e2012-04-08 07:04

24 楼

不用 dp，这个 greedy 就可以解了。
思路就类似 strstr 的解法。

【在 p*****2 的大作中提到】

:
: m*n就是dp了吧？

t*e2012-04-08 07:04

25 楼

How about regular expression matching? The worst case is also exponential. I
used DP, it does pass the large data set. But, is this the best solution?

【在 i**********e 的大作中提到】

: 不用 dp，这个 greedy 就可以解了。
: 思路就类似 strstr 的解法。

k*y2012-04-08 07:04

26 楼

请问像 s = "abadabadabadeabecd", p = "*ab?c*d"这样的不用递归怎么办？
我也贴一个，大家帮忙看看，谢谢~
===========================
bool isMatch(const char* s, const char* p) {
if(*s == 0) return !hasNonStar(p);
if(*p == 0) return false;
if(*p != '*'){ //case: *p != '*'
while(*s && *p && *p!='*') {
if(*p!='?' && *p!=*s)
return false;
++p; ++s;
}
return isMatch(s, p);
}
else{ // case: *p == '*'
if(!skipStars(s, p)) return false;

if(strchr(p, '*')) { // not the final piece
const char* q = p;
while(*q && *q!='*' && *q!='?') ++q;
string buf(p, q-p);
// copy the substr between * and ?or* for strstr
while(1) {
s = strstr(s, buf.c_str());
if(s) {
if(isMatch(s+(q-p), q))
return true;
else if(*q!='?')
return false;
// not end with '?'
// then only need to match the first

++s;
}
else
return false;
}
}
else // final piece, match from the end
return matchLast(s, p);
}
}
inline bool hasNonStar(const char* p) {
if(*p == 0) return false;
while(*p == '*') ++p;
return *p? true : false;
}
inline bool skipStars(const char* &s, const char* &p) {
while(1) {
while(*p == '*') ++p;
if(*p == '?') {
if(*s == 0) return false; // not enough space for stars
++s; ++p;
}
else
break;
}
return true;
}
inline bool matchLast(const char* s, const char* p) {
const char* t = s; const char* q = p;
while(*t) ++t; while(*q) ++q;
while(q >= p) {
if(t < s) return false; // s is shorter
if(*q!='?' && *t!=*q) return false;
--t; --q;
}
return true;
}

c*g2012-04-08 07:04

27 楼

How about there are several "abc" in s?
For example:
s = "dHIabcHELLOabcWORLDxyz"
p = "d*abc*xyz"

【在 l*********8 的大作中提到】

: 有多个 * 的时候，程序时间就指数级增长了。
: 可以考虑如下方案：
: 当遇到 * 的时候，找出该 * 后面紧接的非*字符，记其为一个字符串u, 然后在s中
: 寻找字符串u，
: 比如：
: s = "daaaabcdxdxyz"
: p = "d*abc*xyz"
: 当碰到第一个*的时候，在"aaaabcdxdxyz"找"abc"，
: 找到之后，接着匹配"dxdxyz"和"*xyz"

c*g2012-04-08 07:04

28 楼

I guess there is a little error:
else if(*p=='?' || *p==*s)
return isMatch(s+1,p+1);
How about the both are '*'?

class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
if(*s=='\0'){
if(*p=='\0')
return true;
else if(*p=='*')
return isMatch(s, p+1);
else
return false;
}
else{
if(*p=='\0')
return false;
else if(*p=='?' || *p==*s)
return isMatch(s+1,p+1);
else if(*p=='*')
return isMatch(s+1,p) || isMatch(s,p+1);
else
return false;
}
}
};

【在 g*********e 的大作中提到】

c*g2012-04-08 07:04

29 楼

突然发现好像大家默认s字符串里没有?和*.
好像原题没这么说吧。如果s字符串里没有?和*，问题会比“s字符串里没有?和*”简单
很多。
贴出原题：
Wildcard Matching
Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false

【在 g*********e 的大作中提到】

d*n2012-04-08 07:04

30 楼

Here is a iterative one. I know there is another iterative one which is more
compact.
bool isMatch(const char *str, const char *pattern) {
const char *pstr = str, *pp = pattern;
bool findStar = false;
while (*pstr && *pp) {
if (*pp == '*') {
str = pstr;
pattern = pp + 1;
findStar = true;
}
if (*pstr == *pp || *pp == '?') {
pstr++;
pp++;
continue;
}
if (*pp == '*') {
pp++;
}
else {
if (!findStar) {
return false;
}
pstr= ++str;
pp = pattern;
}
}
while(*pp && *pp == '*') {
findStar = true;
pp++;
}
if (*pp) {
return false;
}
if (!findStar) {
if (*pstr) return false;
}
else {
while (*pstr) ++pstr;
while(*pp != '*' && pstr >= str) {
if (*pp != *pstr && *pp != '?') {
return false;
}
--pp;
--pstr;
}
}
return true;
}