由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - 题目: string pattern matching w/ wildcard (.*)
相关主题
求帮忙看看哪里有问题!strstr的复杂度和worst case是什么?
请问怎么能把代码写得简洁?F电面
Facebook phone screenImplement strStr() ?
说好得FG面经,回馈板上GGJJ能不能讨论一下kmp
onsite遇到的几个面试题三哥题刷的不赖啊
fb电话面试放c code求老师傅指教
也说两个面试题分享A公司面经
贡献个facebook电话interview请教一道c/c++题 (转载)
相关话题的讨论汇总
话题: str2话题: mtch话题: str话题: null话题: printf
进入JobHunting版参与讨论
1 (共1页)
j*****g
发帖数: 223
1
Write a function:
bool match(const char *string, const char *pattern),
where pattern can contain '.' (exact one arbitrary char match) and/or '*' (
zero of more arbitrary char match).
网上看了不少答案,要么是recursive, 慢的要死,要么绝大多数non-recursive的算
法是错的。我有一个DP(dynamic programing)的解答(not sure it's completely
correct or not),不知道各位大侠有什么高招?
d**e
发帖数: 6098
2
贴出来看看?
这个跟strstr类似吧?
O(nm)
n = strlen(string)
m = strlen(pattern)

【在 j*****g 的大作中提到】
: Write a function:
: bool match(const char *string, const char *pattern),
: where pattern can contain '.' (exact one arbitrary char match) and/or '*' (
: zero of more arbitrary char match).
: 网上看了不少答案,要么是recursive, 慢的要死,要么绝大多数non-recursive的算
: 法是错的。我有一个DP(dynamic programing)的解答(not sure it's completely
: correct or not),不知道各位大侠有什么高招?

j*****g
发帖数: 223
3
// txt -> text
// p -> pattern (include . and *)
void pattern_match(const char *txt, const char *p)
{
int **d = NULL;
int len_txt = 0, len_p = 0;
int i, j, k;
if (!txt || !p) goto exit;
len_txt = strlen(txt);
len_p = strlen(p);
if (len_txt == 0 || len_p == 0) goto exit;
printf("text : %s\n", txt);
printf("pattern: %s\n", p);
d = new int*[len_p];
if (!d) goto exit;
memset(d, NULL, sizeof(int*) * len_p);
for (i = 0; i < len_p; i++)
{
d[i] = new int[len_txt];
if (!d[i]) goto exit;
memset(d[i], 0, sizeof(int) * len_txt);
}
for (i = 0; i < len_p; i++)
{
for (j = 0; j < len_txt; j++)
{
if ((txt[j] == p[i] || p[i] == '.') && p[i] != '*')
{
if (i > 0 && j > 0)
{
d[i][j] = d[i - 1][j - 1];
}
else if (i == 0 && j > 0)
{
d[i][j] = 0;
}
else if (i > 0 && j == 0)
{
d[i][j] = 1;
for (k = 0; k < i; k++)
{
if (p[k] != '*')
{
d[i][j] = 0;
break;
}
}
}
else
{
d[i][j] = 1;
}
}
else if (p[i] == '*')
{
if (i > 0)
{
d[i][j] = 0;
for (k = 0; k < i; k++)
{
if (d[k][j] == 1)
{
d[i][j] = 1;
break;
}
}
}
else
{
d[i][j] = 1;
}
}
else
{
d[i][j] = 0;
}
}
}
printf("matrix :\n");
for (i = 0; i < len_p; i++, printf("\n"))
{
for (j = 0; j < len_txt; j++)
{
printf("%3d", d[i][j]);
}
}
printf("result : %s\n", d[len_p - 1][len_txt - 1] == 1 ? "yes" : "no");
exit:
if (d)
{
for (i = 0; i < len_p; i++)
{
if (d[i])
{
delete[] d[i];
d[i] = NULL;
}
}
delete[] d;
d = NULL;
}
}
j*****g
发帖数: 223
4
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]
i**********e
发帖数: 1145
5
Here's a non-recursive solution:
http://www.drdobbs.com/architecture-and-design/210200888
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 j*****g 的大作中提到】
: Write a function:
: bool match(const char *string, const char *pattern),
: where pattern can contain '.' (exact one arbitrary char match) and/or '*' (
: zero of more arbitrary char match).
: 网上看了不少答案,要么是recursive, 慢的要死,要么绝大多数non-recursive的算
: 法是错的。我有一个DP(dynamic programing)的解答(not sure it's completely
: correct or not),不知道各位大侠有什么高招?

d**e
发帖数: 6098
6
不递归,O(nm)时间,O(1)空间的
n = strlen(str)
m = strlen(pattern) if pattern has no *, else n
j*****g
发帖数: 223
7
Hm...看着像suffix tree. 研究研究.....
s*****s
发帖数: 157
8
我的一个onsite死在这个问题上, 20分钟根本做不出来, 最后也就刚处理完*或者?的情
况. 那个老印在旁边得意的晃脑袋
我觉得如果以前没见过这题, 当场做出来的, 那是太牛了
j*****g
发帖数: 223
9
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, originally I came up with another "counter" example string=abbc,
pattern=*bc, but seems your algorithm does work against this example :)

【在 d**e 的大作中提到】
: 不递归,O(nm)时间,O(1)空间的
: n = strlen(str)
: m = strlen(pattern) if pattern has no *, else n

d**e
发帖数: 6098
10
谢谢。
你说的情况我都没考虑过,回头再仔细想想。

like

【在 j*****g 的大作中提到】
: 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?

相关主题
fb电话面试strstr的复杂度和worst case是什么?
也说两个面试题F电面
贡献个facebook电话interviewImplement strStr() ?
进入JobHunting版参与讨论
i**********e
发帖数: 1145
11
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)
p2++;
if (!*p2) return false;
p1++;
p2++;
}
return *p2 == '\0';
}
Some test cases:
assume the string is "hello".
pattern result
j*****g
发帖数: 223
12
hm...
1. counter example: str=a, pattern=.
2. counter example: str=aac, pattern=*ac
d******a
发帖数: 238
13
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
14
What company is that? :-)

【在 s*****s 的大作中提到】
: 我的一个onsite死在这个问题上, 20分钟根本做不出来, 最后也就刚处理完*或者?的情
: 况. 那个老印在旁边得意的晃脑袋
: 我觉得如果以前没见过这题, 当场做出来的, 那是太牛了

i**********e
发帖数: 1145
15
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
16
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 :)

.

【在 i**********e 的大作中提到】
: 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
17
Don't have that book right now. Mind posting here? Thx!
J

could

【在 d******a 的大作中提到】
: This problem is from the first chapter of book <>. You could
: have a look. I think the solution in that book is pretty good.

i**********e
发帖数: 1145
18
Are you going to interview candidates soon?
StrStr implementation is much easier to solve compared to wildcard matching.
Although the wildcard matching is a very tricky question, Facebook had asked
this question before:
http://www.mitbbs.com/article_t/JobHunting/31575425.html
If you have taken part in Google Codejam before, you will know how fast
those crazy smart people solve problems within minutes. To solve this
problem using nothing but paper and pencil + without bugs in 20 minutes is
very very difficult, but is certainly possible for very very good candidates.
Here's my implementation of StrStr using brute force, O(N*M), N = length of
str, M = length of target.
char* StrStr(char *str, char *target) {
if (!*target) return str; // check special case
char *p1 = str, *p2 = target;
while (*p1) {
char *p1Begin = p1;
while (*p1 && *p2 && *p1 == *p2) {
p1++;
p2++;
}
if (*p2) {
p2 = target;
p1 = p1Begin + 1;
} else {
return p1Begin;
}
}
return NULL;
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

fine.

【在 j*****g 的大作中提到】
: 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
19
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 的大作中提到】
: Are you going to interview candidates soon?
: StrStr implementation is much easier to solve compared to wildcard matching.
: Although the wildcard matching is a very tricky question, Facebook had asked
: this question before:
: http://www.mitbbs.com/article_t/JobHunting/31575425.html
: If you have taken part in Google Codejam before, you will know how fast
: those crazy smart people solve problems within minutes. To solve this
: problem using nothing but paper and pencil + without bugs in 20 minutes is
: very very difficult, but is certainly possible for very very good candidates.
: Here's my implementation of StrStr using brute force, O(N*M), N = length of

i**********e
发帖数: 1145
20
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

==

【在 j*****g 的大作中提到】
: 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

相关主题
能不能讨论一下kmp分享A公司面经
三哥题刷的不赖啊请教一道c/c++题 (转载)
放c code求老师傅指教请问strcpy()和memcpy()的写法问题
进入JobHunting版参与讨论
i**********e
发帖数: 1145
21
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

==

【在 j*****g 的大作中提到】
: 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

P********l
发帖数: 452
22
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, mtch[i][j]=mtch[i-1][j-1]
4. otherwise, not matched.
package solution.string;
public class WildcardMatching {
boolean mtch[][];
/**
* check if patt matches the string str.
*
* @param str
* the string to match
* @param patt
* the pattern matching str. '*' is for 0 or more characters
and
* '.' is for exactly one characters.
* @return
*/
public boolean match(String str, String patt) {
if (str == null || patt == null)
return false;
// convert them to arrays
// string to match
char[] cstr = str.toCharArray();
// pattern to match cstr
char[] cpatt = patt.toCharArray();
// create a boolean array of [0..len(cstr)][0..len(cpatt)]
// initialize the elements of mtch[0][*] and mtch[*][0] to false
// mtch[0][0] is true
mtch = new boolean[cstr.length + 1][];
for (int i = 0; i <= cstr.length; i++) {
mtch[i] = new boolean[cpatt.length + 1];
}
mtch[0][0] = true;
if (cpatt.length > 0 && cpatt[0] == '*')
mtch[0][1] = true;
// check if the pattern cstr matches the string cstr
for (int i = 0; i < cstr.length; i++) {
boolean matched = false;
for (int j = 0; j < cpatt.length; j++) {
if (cpatt[j] == '.') {
// the previous matching status (i,j) determine current
// status (i+1,j+1)
mtch[i + 1][j + 1] = mtch[i][j];
} else if (cpatt[j] == '*') {
// the previous matching status (i,*) determine current
// status (i+1,j+1)
mtch[i + 1][j + 1] = mtch[i][j] || mtch[i][j + 1];
} else {
// the current status (i+1,j+1) is determined by current
// character match and previous match
mtch[i + 1][j + 1] = (cstr[i] == cpatt[j]) && mtch[i][j];
}
matched |= mtch[i + 1][j + 1];
}
if (!matched)
break;
}
return mtch[cstr.length][cpatt.length];
}
}
Test cases:
WildcardMatching wm = new WildcardMatching();
Assert.assertTrue(wm.match("this is a test", "t*t"));
Assert.assertTrue(wm.match("this is a test", "*t"));
Assert.assertTrue(wm.match("this is a test", "t**"));
Assert.assertTrue(wm.match("this is a test", "this is...test"));
Assert.assertTrue(wm.match("this is a test", "*"));
Assert.assertTrue(wm.match("this is a test", "t.*.t"));
Assert.assertTrue(wm.match("this is a test", "t.*t*t"));
Assert.assertTrue(wm.match("this is a test", "*this is a test"));
// Assert.assertTrue(wm.match("abc", ""));
Assert.assertFalse(wm.match("this is a test", ""));
Assert.assertFalse(wm.match("this is a test", "this is a tesx"));
Assert.assertFalse(wm.match("this is a test", ".this is a test"));
Assert.assertFalse(wm.match("this is a test", "ti.s is a test"));
Assert.assertFalse(wm.match("this is a test", "*tesx"));
Assert.assertFalse(wm.match("this is a test", "t*x"));
Assert.assertFalse(wm.match("this is a test", "x*"));
Assert.assertFalse(wm.match("this is a test", "*x"));
Any comment?
P********l
发帖数: 452
23
Same as previous version but only 1-dimension array is used.
time complexity is still O(mn).
You can check the code here:
http://code.google.com/p/sureinterview/source/browse/src/solution/string/WildcardMatching.java
After you logged in, you can conveniently put comments on the 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 character.
* @return
*/
public boolean match2(String str, String patt) {
if (str == null || patt == null)
return false;
// convert them to arrays
// string to match
char[] cstr = str.toCharArray();
// pattern to match cstr
char[] cpatt = patt.toCharArray();
// create a boolean array of [0..len(cpatt)]
// initialize the elements of mtch[*] to false
// mtch[0] is true
mtch2 = new boolean[cpatt.length + 1];
mtch2[0] = true;
if (cpatt.length > 0 && cpatt[0] == '*')
mtch2[1] = true;
// check if the pattern cstr matches the string cstr
for (int i = 0; i < cstr.length; i++) {
boolean matched = false;
// calculate from right to left to preserve the previous status.
for (int j = cpatt.length - 1; j >= 0; j--) {
if (cpatt[j] == '.') {
mtch2[j + 1] = mtch2[j];
} else if (cpatt[j] == '*') {
mtch2[j + 1] = mtch2[j] || mtch2[j + 1];
} else {
mtch2[j + 1] = (cstr[i] == cpatt[j]) && mtch2[j];
}
matched |= mtch2[j + 1];
}
if (!matched)
return false;
}
return mtch2[cpatt.length];
}
i**********e
发帖数: 1145
24
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 的大作中提到】
: Same as previous version but only 1-dimension array is used.
: time complexity is still O(mn).
: You can check the code here:
: http://code.google.com/p/sureinterview/source/browse/src/solution/string/WildcardMatching.java
: After you logged in, you can conveniently put comments on the code.
: /**
: * check if patt matches the string str. Same as {@link match} but
: * one-dimension array is used.
: *
: * @param str

P********l
发帖数: 452
25
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 character.
* @return true, if the pattern matches the string. otherwise, false.
*/
public boolean match2(String str, String patt) {
if (str == null || patt == null)
return false;
// convert them to arrays
char[] cstr = str.toCharArray();
char[] cpatt = patt.toCharArray();
// create a boolean array of [0..len(cpatt)]
// initialize the elements of mtch[*] to false
// mtch[0] is true
mtch2 = new boolean[cpatt.length + 1];
mtch2[0] = true;
for (int i = 0; i < cpatt.length && cpatt[i] == '*'; i++)
mtch2[i + 1] = true;
// check if the pattern cstr matches the string cstr
for (int i = 0; i < cstr.length; i++) {
boolean matched = false;
// calculate from right to left to preserve the previous status.
for (int j = cpatt.length - 1; j >= 0; j--) {
if (cpatt[j] == '*') {
mtch2[j + 1] = mtch2[j] || mtch2[j + 1];
} else {
mtch2[j + 1] = ((cpatt[j] == cstr[i]) || (cpatt[j] == '.
'))
&& mtch2[j];
// if current character matches, update the following '*
' in
// patter because they can match a 0-length char.
if (mtch2[j + 1]) {
for (int k = j + 1; (k < cpatt.length)
&& cpatt[k] == '*'; k++) {
mtch2[k + 1] = true;
}
}
}
matched |= mtch2[j + 1];
}
if (!matched)
return false;
mtch2[0] = false;
}
return mtch2[cpatt.length];
}

【在 i**********e 的大作中提到】
: 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.

i**********e
发帖数: 1145
26
我找不到任何错误。相信是正解了呵呵~
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 P********l 的大作中提到】
: 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.

i**********e
发帖数: 1145
27
另外,这是我的重写的新代码,我觉得比我之前的版本要简洁些。
而且这版本也处理'.'为一个任意字母。
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++;
}
if (!*p1) return true;
// Now *p1 must be a character. Find the first same character, could be
'\0' == '\0'
const char *s1 = p1, *s2 = p2;
while (*p1 != '*') {
if (!*p1 && !*p2) return true;
if (!*p2) return false;
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;
}
if (*p1 == '.' || *p1 == *p2) {
p1++;
p2++;
} else {
p1 = s1;
p2 = ++s2;
}
}
}
}
一些常见面试题的答案与总结 -
http://www.ihas1337code.com
P********l
发帖数: 452
28
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 is super confusing.
i**********e
发帖数: 1145
29
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

【在 P********l 的大作中提到】
: 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) {

j*****g
发帖数: 223
30
想出来个新方法,至少看上去挺简单的,不用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:
str1*str2*str3*str4,
那我们只要先把str1和str4跟target string的头尾匹配了,剩下的就是case 1. 如果
只有一头是str另一头是*, 同理解决.
哈哈!!
相关主题
Wolver, 如何用C把一个string里的每个字符读出来?请问怎么能把代码写得简洁?
根据我面过的hp来的人,基本都没竞争力Facebook phone screen
求帮忙看看哪里有问题!说好得FG面经,回馈板上GGJJ
进入JobHunting版参与讨论
P********l
发帖数: 452
31
可以和ihasleetcode的算法同归于有限状态机一类。再往下走就是对pattern进行编译
了。

【在 j*****g 的大作中提到】
: 想出来个新方法,至少看上去挺简单的,不用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)
: {

j*****g
发帖数: 223
32
Agree.
Just felt this approach is fairly *simple and easy to remember*. So sharing
my thoughts here.
c***2
发帖数: 838
33
Here's my program, please help check whether I miss anything.
c***2
发帖数: 838
34
Here's my program, please help check whether I miss anything.
j*****g
发帖数: 223
35
大哥,
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 的大作中提到】
: Here's my program, please help check whether I miss anything.
c***2
发帖数: 838
36
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
37

man strstr
char *strstr(const char *haystack, const char *needle);

【在 j*****g 的大作中提到】
: 大哥,
: 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
38
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;

return 0;
}
char *strstrndots(const char *haystack, const char *needle, int n)
{
while(*haystack){
if(matchndots(haystack++,needle,n))
return (char*)(haystack-1);
}

return NULL;
}
char *strstrwilddots(const char *haystack, const char *needle)
{
const char *p=needle;
int len, matched=0;
const char *pm, *pstart,*pm1;

pm1=haystack;
while(*p && *haystack){
/* skip leading *'s */
while(*p && (*p=='*')){
p++;
}
if(!(*p)) return (char*)pm1;

pstart=p;
len=0;
// get a sunstring from needle where substring does not contain any *
while(*p && (*p!='*')){
p++;
len++;
}

pm=strstrndots(haystack, pstart, len);
if(!pm)
return NULL; // no match
else
matched++;

if(!(*p)) {//scanned through needle
if(matched==1)
return (char*)pm;
else
return (char*)pm1;
}

if(matched==1)
pm1=pm;

while(*haystack && len){
haystack++;
len--;
}
if(len) return NULL; //run out of haystack
}

return NULL;
}
int main (int argc, char *argv[])
{
char str[STR_SIZE],str2[STR_SIZE];
char *p;

strcpy(str,"mississippi");
strcpy(str2,"....iss..pi");
printf("Text=%s\n",str);
if(matchndots(str,str2,strlen(str2)))
printf("match(%s)=Yes\n",str2);
else
printf("match(%s)=No\n",str2);

strcpy(str2,"iss..");
printf("Text=%s\n",str);
p=strstrndots(str,str2,strlen(str2));
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"miss");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"mass");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"sip");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"spp");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*sip");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*sip..");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*sip...");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*sip*");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*iss*ip");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*i.s*i.");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

strcpy(str2,"*iss*ii");
printf("\nText=%s\n",str);
p=strstrwilddots(str,str2);
if(p)
printf("match(%s)=%s\n",str2, p);
else
printf("match(%s)=NULL\n",str2);

return 0;
}
/*
Text=mississippi
match(....iss..pi)=Yes
Text=mississippi
match(iss..)=ississippi
Text=mississippi
match(miss)=mississippi
Text=mississippi
match(mass)=NULL
Text=mississippi
match(sip)=sippi
Text=mississippi
match(spp)=NULL
Text=mississippi
match(*)=mississippi
Text=mississippi
match(*sip)=sippi
Text=mississippi
match(*sip..)=sippi
Text=mississippi
match(*sip...)=NULL
Text=mississippi
match(*sip*)=sippi
Text=mississippi
match(*iss*ip)=ississippi
Text=mississippi
match(*i.s*i.)=ississippi
Text=mississippi
match(*iss*ii)=NULL
*/
s*****n
发帖数: 5488
39
这题看上去可以从kMP变化得到一个解。
如果是一个., 那么KMP的prefix 表对应项++.
如果是一个*,那么happy了,或者match,或者从不match那里从新开始。
应该是O(n)算法。
j*****g
发帖数: 223
40
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

【在 s*****n 的大作中提到】
: 这题看上去可以从kMP变化得到一个解。
: 如果是一个., 那么KMP的prefix 表对应项++.
: 如果是一个*,那么happy了,或者match,或者从不match那里从新开始。
: 应该是O(n)算法。

1 (共1页)
进入JobHunting版参与讨论
相关主题
请教一道c/c++题 (转载)onsite遇到的几个面试题
请问strcpy()和memcpy()的写法问题fb电话面试
Wolver, 如何用C把一个string里的每个字符读出来?也说两个面试题
根据我面过的hp来的人,基本都没竞争力贡献个facebook电话interview
求帮忙看看哪里有问题!strstr的复杂度和worst case是什么?
请问怎么能把代码写得简洁?F电面
Facebook phone screenImplement strStr() ?
说好得FG面经,回馈板上GGJJ能不能讨论一下kmp
相关话题的讨论汇总
话题: str2话题: mtch话题: str话题: null话题: printf