j*****g
发帖数: 223 | 1 Meaning of d[i, j] (I should've used bool instead of integer, but you get
the idea):
d[i, j]
= 0, if txt[0...j] doesn't match pattern p[0...i]
= 1, if txt[0...j] matches pattern p[0...i] |
|
|
d**e
发帖数: 6098 | 3 不递归，O(nm)时间，O(1)空间的
n = strlen(str)
m = strlen(pattern) if pattern has no *, else n |
|
j*****g
发帖数: 223 | 4 Hm...看着像suffix tree. 研究研究..... |
|
s*****s
发帖数: 157 | 5 我的一个onsite死在这个问题上, 20分钟根本做不出来, 最后也就刚处理完*或者?的情
况. 那个老印在旁边得意的晃脑袋
我觉得如果以前没见过这题, 当场做出来的, 那是太牛了 |
|
j*****g
发帖数: 223 | 6 Still looking at @ihasleetcode suggested Dr.Dobbs algorithm which looks like
a suffix tree matching.
As for @done, does your algorithm pass on this test case?
string : abc
pattern: b*
It's a not match. But in your code, the inner loop will break out when
comparing 'a' vs 'b'. after breaking out, the outer loop will advance s
pointer, so next time, p1 will be pointing at 'b', and s1 will be pointing
at 'b'. After that, seems your algorithm will match them and return 1.
Can you double check?
BTW, ... 阅读全帖 |
|
d**e
发帖数: 6098 | 7 谢谢。
你说的情况我都没考虑过，回头再仔细想想。
like |
|
i**********e
发帖数: 1145 | 8 No need suffix tree or any advanced data structure. No need dynamic
programming. All you need is two pointers,
iterating through the pattern and string at the same time. Need to take
extra care for special cases.
I have wrote the code below:
bool match(const char *str, const char *pattern) {
const char *p1 = pattern, *p2 = str;
if (*p1 && *p1 != '*' && *p1 != *p2)
return false;
while (*p1) {
while (*p1 == '*')
p1++;
if (!*p1) return true;
while (*p2 && *p1 != *p2)
... 阅读全帖 |
|
j*****g
发帖数: 223 | 9 hm...
1. counter example: str=a, pattern=.
2. counter example: str=aac, pattern=*ac |
|
d******a
发帖数: 238 | 10 This problem is from the first chapter of book <>. You could
have a look. I think the solution in that book is pretty good. |
|
c***2
发帖数: 838 | 11 What company is that? :-) |
|
i**********e
发帖数: 1145 | 12 hmm...
This problem seem not that straightforward. Lots of tricky cases to handle.
Anyone who can code this in 20 minutes and got it correct, I salute you.
I have added some more test cases below:
str = "mississippi"
pattern result |
|
j*****g
发帖数: 223 | 13 I felt my DP solution is the right one. Though I coded it up in about 2
hours (coding is really only 20min, but finding the solution took many
trials and many brain cells).
Anyway, I'm not sure such problems are good interview question candidates.
It's beyond anyone's raw brain power to come up with correct solution from
scratch within given time frame.
My typical interview question is write strstr and using double loop is fine.
Still surprisingly lots of SDE candidates failed w/ that :)
. |
|
j*****g
发帖数: 223 | 14 Don't have that book right now. Mind posting here? Thx!
J
could |
|
j*****g
发帖数: 223 | 15 That's good, with a minor bug that you didn't do error check on target,str==
NULL case.
Yes, there are always very strong candidates out there, those have IOI/ACM
background can certainly solve difficult problems fast. Still most time in
my oponion, such problems are testing candidates' familarity of these
problems not raw brain power.
J
matching.
asked
candidates.
of |
|
i**********e
发帖数: 1145 | 16 Thanks for pointing that out the special case, which in fact I didn't check
for target==NULL when coding it for the first time.
When str==NULL,the code will still work, as it won't even go into the loop.
Therefore, it will return NULL in this case, which is still true.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
== |
|
i**********e
发帖数: 1145 | 17 I just realized the above code will crash if NULL is passed into the
function, because I forgot to check for NULL case.
Thanks for pointing out that.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
== |
|
P********l
发帖数: 452 | 18 How about this version using Dynamic Programming?
The basic idea is fill in a table for a matching path. If the last pair
matches, the whole string will match.
mtch is the array, which is of (string length + 1)*(pattern length + 1).
mtch[0][*] and mtch[*][0] is padded with false.
Then the function is something like:
mtch[i][j] =
1. if pattern char='.', mtch[i][j]=mtch[i-1][j-1]
2. if pattern char='*', mtch[i][j]=mtch[i-1][j-1] || mtch[i][j]=mtch[i-1][
j]
3. if pattern char=string char, mtc... 阅读全帖 |
|
|
i**********e
发帖数: 1145 | 20 Great attempt.
I think you have a pretty good approach here using DP.
However, I think you still missed few test cases:
Try pattern "*o*" and string "hello", it should return true.
and pattern "a" and string "aa", it should return false. |
|
P********l
发帖数: 452 | 21 Fixed the issue ihasleetcode mentioned. Thanks.
Added more test cases like:
string = "ho"
pattern = "**ho", "ho**"
string = "a", pattern = "aa"
string = "aa", pattern = "a"
Code:
/**
* check if patt matches the string str. Same as {@link match} but
* one-dimension array is used.
*
* @param str
* the string to match
* @param patt
* the pattern matching str. '*' is for 0 or more characters
and
* '.' is for exactly one cha... 阅读全帖 |
|
|
i**********e
发帖数: 1145 | 23 另外，这是我的重写的新代码，我觉得比我之前的版本要简洁些。
而且这版本也处理'.'为一个任意字母。
bool match(const char *str, const char *pattern) {
const char *p1 = pattern, *p2 = str;
// If the first character is a letter, need to match letter by letter.
while (*p1 != '*') {
if (!*p1 && !*p2) return true;
if (!*p1 || !*p2) return false;
if (*p1 == '.' || *p1 == *p2) {
p1++;
p2++;
} else {
return false;
}
}
while (true) {
// Now *p1 must be '*'
while (*p1 && *p1 == '*') {
p1++;
... 阅读全帖 |
|
P********l
发帖数: 452 | 24 What's the purpose of following code? It works just fine without it.
if (!*p1) {
// the code below is doing the same as: s2 = s2+strlen(s2)-strlen(s1
);
const char *t1 = s1, *t2 = s2;
while (*t1++)
t2++;
while (*t2++)
s2++;
while (*s1) {
if (*s1 == '.' || *s1 == *s2) {
s1++;
s2++;
} else {
return false;
}
}
return true;
}
The single letter variables ... 阅读全帖 |
|
i**********e
发帖数: 1145 | 25 The purpose of the code is to match the end of the string with the pattern:
For example,
pattern="h*llo"
string="hellohellc"
The code will ensure that if the last character is not a '*', then it will
match the last section letter by letter.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
s1 |
|
j*****g
发帖数: 223 | 26 想出来个新方法，至少看上去挺简单的，不用recursion, 动态规划，suffix tree, 或
脑筋急转弯的算法。
case 1。看看一个普通的pattern string (not edge case):
*str1*str2*str3*
where 1) strN is basically a-z plus '.' 2) assume we've already collapsed
multiple consecutive *'s into a single *.
在这种情况下, 去匹配target string就是一个贪心算法:
start = target;
foreach (strN)
{
new_start = strstr(target + start, strN);
if (new_start == NULL) return false;
start = new_start + len(strN) + 1;
}
return true;
case 2。再看看其他pattern string的情况:
如果pattern string is like... 阅读全帖 |
|
P********l
发帖数: 452 | 27 可以和ihasleetcode的算法同归于有限状态机一类。再往下走就是对pattern进行编译
了。 |
|
j*****g
发帖数: 223 | 28 Agree.
Just felt this approach is fairly *simple and easy to remember*. So sharing
my thoughts here. |
|
c***2
发帖数: 838 | 29 Here's my program, please help check whether I miss anything. |
|
c***2
发帖数: 838 | 30 Here's my program, please help check whether I miss anything. |
|
j*****g
发帖数: 223 | 31 大哥，
1）能不能用点通俗的变量名？haystack/needle俺看不懂
2）matchdots，你是不是肯定text和dstr的长度一样？一个简单的字符串比较写成这样
，会不会out of bound and access violation呢？
3）strstrwilddots没有error/NULL checking
4）matched好像一直在++，怎么后面的比较都是matched == 1?
5）你的解答好像有点文不对题？说的是一个pattern能不能match整个string， 不时一
部分.
不过大概的意思我看懂了，是这个贪心算法. |
|
c***2
发帖数: 838 | 32 1) that's borrowed from stardard C lib
2) just as memcmp, but handles .... NO
3) already checked by the codes
4) only remember the first match
5) my program covers more than that. :-) |
|
r***u
发帖数: 241 | 33
man strstr
char *strstr(const char *haystack, const char *needle); |
|
c***2
发帖数: 838 | 34 Here's the full file. You may compile and run: any case I missed?
==================================================================
/* wild.c
*/
#include
#include
#include
#define STR_SIZE 256
//===========================================================
int matchndots(const char *text, const char *dstr, int len)
{
while(len&&*text&&*dstr&&(*text==*dstr || *dstr=='.')){
text++;
dstr++;
len--;
}
if(!len)
return 1;
... 阅读全帖 |
|
s*****n
发帖数: 5488 | 35 这题看上去可以从kMP变化得到一个解。
如果是一个., 那么KMP的prefix 表对应项++.
如果是一个*,那么happy了，或者match，或者从不match那里从新开始。
应该是O（n)算法。 |
|
j*****g
发帖数: 223 | 36 Yes.
Since the problem reduces to do a bunch of strstr, so it should be linear to
O(n+m) where n is string length and m is the pattern length.
J |
|
j******4
发帖数: 116 | 37 不是啊。 那个是wildcard match, 一个loop 就可以了。
这个是 regex.
没人有兴趣？ 自己顶一下。 |
|
j******4
发帖数: 116 | 38 wildcard match一个loop就可
恩，说的不够细， main loop 有一个， 但是需要retract, 所以总的cost 应该是 O(
mn).
谢谢。 |
|
j*****g
发帖数: 223 | 39 写的好，是一格比较搞的题目。
But so far I haven't seen your brute force solution O(N*M) yet...Perhaps I
missed it?
J |
|
i**********e
发帖数: 1145 | 40 我已经写了，但是感觉不是最简洁的，所以就没好意思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 *p... 阅读全帖 |
|
D********g
发帖数: 650 | 41 这题如果用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
发帖数: 1145 | 42 思路基本上是对的，但是要写对很不容易。
你有没有考虑过这几个case?
h*o match hello
ll*o does not match hello
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
D********g
发帖数: 650 | 43 对，这些edge case要找全确实不容易。
我觉得如果pattern是在string的头尾，则特殊处理一下，问题也不大。 |
|
i**********e
发帖数: 1145 | 44 是不容易呀。
所以我觉得这题真是很好的练习题，提高你的编程能力。
我换了几次写法，每次用稍微不同的思路重写了一下，每次都还是会出些小bug，能练
到第一次就能写对真的很不容易。
而且制造test cases所花的时间绝对是比编程还要困难的。
一些常见面试题的答案与总结 -
http://www.ihas1337code.com |
|
w***o
发帖数: 109 | 45 你就是那位1337大神？太感谢你了，leetcode帮了我很多！！
对于你关于test case的高论真是太有同感了，记得有一次板上讨论关于interleaving
string的问题，我感觉可以有O（n）的解法，化了很长时间写了一个，结果通过了
small judge，但large judge有三个case死活过不来。要不是你那些cover了所有case
，我还真以为自己找到一个好的算法了。 |
|
h****n
发帖数: 1093 | 46 说的很对，写出考虑到所有可能的情况的test case的确很不容易
最近才开始做OJ，收获很大，特别感谢作者能想出那么多test cases出来验证自己的程序
想必是花了挺多时间的 |
|
|
|
i**********e
发帖数: 1145 | 49 small judge 过了而没过 large 肯定是漏了某些状况没测好。
如果你还有当时那个代码，请问可以发一份给我吗？
这样我可以针对更全面的测试来设计 small case 。
interleaving
case |
|
|
