i**********e
发帖数: 1145 | 1 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O(N*M),N=string的长度，M=pattern的长度。
另外，可以调用C library 里面的 strstr() 函数，会对这题有大大的辅助。
我一直都在思考有没有O(N)的解法，结果在DrDobbs网站上看到一个据说O(N)的解法。
（之前都在DrDobbs网站上看了一些质量很好的文章，所以还蛮信任那网站的）
http://www.drdobbs.com/architecture-and-design/210200888
我想这有点不可思议，因为他的解法非常直接，应该是brute force的解法。
我对此感到非常怀疑，所以就制造了很多test cases，全都一一pass了。
我还是不放弃，终于皇天不负苦心人，这个test case fail 了。
就是：
pattern = "*aabbaa*a*"
string = "aaabbaabbaab"
正解应该是返回 True，结果那文章里的code的返回值是 False。
总结：
我的结论就是，网上的资料和书本上的都不一定完全对的，一定要充分过滤呀。尤其是
网上的代码，我真的看过太多网上代码都有bug的 -.-
还有另外一个结论就是，写test case真的比写程序还要难，还要耗时。这是因为写好的test case必须对算法有非常充分的掌握，知道哪一些是要特别注意的corner case。多多练习在纸上写程序并且要求能第一次写对，制造大量的test cases，相信你的写程序能力会大大提升。
这题我总结就是，由于string matching的关系，brute force的解法不可能是O(N)的。
只有利用Knuth-Morris-Pratt或者Boyer-Moore algorithm才能把复杂度降低成O(N)。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
j*****g
发帖数: 223 | 2 写的好，是一格比较搞的题目。
But so far I haven't seen your brute force solution O(N*M) yet...Perhaps I
missed it?
J |
i**********e
发帖数: 1145 | 3 我已经写了，但是感觉不是最简洁的，所以就没好意思post上来。
我相信有更简洁的版本，所以我还在努力写更简洁的代码。
感觉上递归的方法可以写的更简洁些，但会更加难写对，尤其这问题细节那么多。
注：我没有处理 ‘.’（‘.’match一个的任意字符）。
bool match(const char *str, const char *pattern) {
const char *p1 = pattern, *p2 = str;
while (*p1 && *p1 != '*') {
if (!*p2) return false;
if (*p1 != *p2)
return false;
p1++;
p2++;
}
if (!*p1) {
if (*p2) return false;
else return true;
}
while (*p1) {
while (*p1 == '*')
p1++;
if (!*p1) return true;
const char *p1s = p1;
const char *p2s = p2;
while (*p1 && *p1 != '*') {
if (!*p2) return false;
if (*p1 == *p2) {
p1++;
p2++;
} else {
p1 = p1s;
p2s++;
p2 = p2s;
}
}
if (!*p1) {
const char *p1end = p1;
p1--;
while (*p2)
p2++;
p2--;
while (p1 >= pattern && *p1 != '*') {
if (p2 < str) return false;
if (*p1 != *p2) return false;
p1--;
p2--;
}
p1 = p1end;
}
}
return true;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 j*****g 的大作中提到】
: 写的好，是一格比较搞的题目。
: But so far I haven't seen your brute force solution O(N*M) yet...Perhaps I
: missed it?
: J
|
D********g
发帖数: 650 | 4 这题如果用strstr的话应该可以greedy。
pseudo code:
bool match(const char *s, const char *pattern)
{
string[] ps = string.split(pattern, '*');
foreach(string p in ps)
{
idx = s.find(p);
if (idx == -1) return false;
s = s.substr(idx + p.length());
}
return true;
}
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
i**********e
发帖数: 1145 | 5 思路基本上是对的，但是要写对很不容易。
你有没有考虑过这几个case?
h*o match hello
ll*o does not match hello
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 D********g 的大作中提到】
: 这题如果用strstr的话应该可以greedy。
: pseudo code:
: bool match(const char *s, const char *pattern)
: {
: string[] ps = string.split(pattern, '*');
: foreach(string p in ps)
: {
: idx = s.find(p);
: if (idx == -1) return false;
: s = s.substr(idx + p.length());
|
D********g
发帖数: 650 | 6 对，这些edge case要找全确实不容易。
我觉得如果pattern是在string的头尾，则特殊处理一下，问题也不大。
【在 i**********e 的大作中提到】
: 思路基本上是对的，但是要写对很不容易。
: 你有没有考虑过这几个case?
: h*o match hello
: ll*o does not match hello
: 一些常见面试题的答案与总结 -
: http://www.ihas1337code.com
|
i**********e
发帖数: 1145 | 7 是不容易呀。
所以我觉得这题真是很好的练习题，提高你的编程能力。
我换了几次写法，每次用稍微不同的思路重写了一下，每次都还是会出些小bug，能练
到第一次就能写对真的很不容易。
而且制造test cases所花的时间绝对是比编程还要困难的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
【在 D********g 的大作中提到】
: 对，这些edge case要找全确实不容易。
: 我觉得如果pattern是在string的头尾，则特殊处理一下，问题也不大。
|
w***o
发帖数: 109 | 8 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
h****n
发帖数: 1093 | 9 说的很对，写出考虑到所有可能的情况的test case的确很不容易
最近才开始做OJ，收获很大，特别感谢作者能想出那么多test cases出来验证自己的程序
想必是花了挺多时间的
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
w****x
发帖数: 2483 | |
|
|
g*********e
发帖数: 14401 | |
i**********e
发帖数: 1145 | 12 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case
【在 w***o 的大作中提到】
: 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
: 对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
: string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
: small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
: ，我还真以为自己找到一个好的算法了。
|
j******2
发帖数: 362 | 13 进来拜拜。牛人加好人。
【在 i**********e 的大作中提到】
: small judge 过了而没过 large 肯定是漏了某些状况没测好。
: 如果你还有当时那个代码，请问可以发一份给我吗？
: 这样我可以针对更全面的测试来设计 small case 。
:
: interleaving
: case
|
l*********8
发帖数: 4642 | 14 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
C***U
发帖数: 2406 | 15 thanks leetcode!!
I like your website.
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
i**********e
发帖数: 1145 | 16 问题背景：
最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
expression match吧。
所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
给个例子，例如
a*b 可以match : ab, aab, aaaaaaaaaaab
写个函数:
bool match(const char *string, const char *pattern)
这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
人很倒霉被问到这题。facebook有问过这题：请参考
http://www.mitbbs.com/article_t/JobHunting/31575425.html
这题其实利用brute force就可以了，算法不难想到，但是要处理很多special case，
非常的棘手。我觉得正常人一般都回遗漏掉很多case，第一次就能写对简直就难如登天
。再加上面试的压力，我觉得没做过这题面试当场第一次就能写对的是神人。
Brute force的算法就是O(N*M),N=string的长度，M=pattern的长度。
另外，可以调用C library 里面的 strstr() 函数，会对这题有大大的辅助。
我一直都在思考有没有O(N)的解法，结果在DrDobbs网站上看到一个据说O(N)的解法。
（之前都在DrDobbs网站上看了一些质量很好的文章，所以还蛮信任那网站的）
http://www.drdobbs.com/architecture-and-design/210200888
我想这有点不可思议，因为他的解法非常直接，应该是brute force的解法。
我对此感到非常怀疑，所以就制造了很多test cases，全都一一pass了。
我还是不放弃，终于皇天不负苦心人，这个test case fail 了。
就是：
pattern = "*aabbaa*a*"
string = "aaabbaabbaab"
正解应该是返回 True，结果那文章里的code的返回值是 False。
总结：
我的结论就是，网上的资料和书本上的都不一定完全对的，一定要充分过滤呀。尤其是
网上的代码，我真的看过太多网上代码都有bug的 -.-
还有另外一个结论就是，写test case真的比写程序还要难，还要耗时。这是因为写好的test case必须对算法有非常充分的掌握，知道哪一些是要特别注意的corner case。多多练习在纸上写程序并且要求能第一次写对，制造大量的test cases，相信你的写程序能力会大大提升。
这题我总结就是，由于string matching的关系，brute force的解法不可能是O(N)的。
只有利用Knuth-Morris-Pratt或者Boyer-Moore algorithm才能把复杂度降低成O(N)。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
w***o
发帖数: 109 | 17 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
h****n
发帖数: 1093 | 18 说的很对，写出考虑到所有可能的情况的test case的确很不容易
最近才开始做OJ，收获很大，特别感谢作者能想出那么多test cases出来验证自己的程序
想必是花了挺多时间的
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
w****x
发帖数: 2483 | |
g*********e
发帖数: 14401 | |
|
|
i**********e
发帖数: 1145 | 21 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case
【在 w***o 的大作中提到】
: 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
: 对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
: string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
: small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
: ，我还真以为自己找到一个好的算法了。
|
j******2
发帖数: 362 | 22 进来拜拜。牛人加好人。
【在 i**********e 的大作中提到】
: small judge 过了而没过 large 肯定是漏了某些状况没测好。
: 如果你还有当时那个代码，请问可以发一份给我吗？
: 这样我可以针对更全面的测试来设计 small case 。
:
: interleaving
: case
|
l*********8
发帖数: 4642 | 23 赞！
question：
如果strstr是o(N)的，那么调用strstr的简单解法也应该是O(n)的吧？
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
C***U
发帖数: 2406 | 24 thanks leetcode!!
I like your website.
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
l**b
发帖数: 457 | 25 大牛出山的终结，看了好多次，一定要mark一下。 |
c********t
发帖数: 5706 | 26 赞研究精神。
这个和OJ上的题不一样吧，似乎还容易些？
【在 i**********e 的大作中提到】
: 问题背景：
: 最近觉得这题挺有意思，就是wildcard string matching，也算比较简单的regular
: expression match吧。
: 所谓的wildcard就是指‘*’,‘*’的意思是可以match 0个或以上的任意字符。
: 给个例子，例如
: a*b 可以match : ab, aab, aaaaaaaaaaab
: 写个函数:
: bool match(const char *string, const char *pattern)
: 这题我觉得当为面试题相对来说偏难吧，应该不会常被问到，但网上搜一搜还是有
: 人很倒霉被问到这题。facebook有问过这题：请参考
|
c********t
发帖数: 5706 | 27 这么好的帖子，怎么沉了两年，幸亏有考古者挖了出来。
interleaving
case
【在 w***o 的大作中提到】
: 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
: 对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
: string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
: small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
: ，我还真以为自己找到一个好的算法了。
|
