# boards

JobHunting版 - 题目: string pattern matching w/ wildcard (.*)

Facebook phone screenImplement strStr() ？

onsite遇到的几个面试题三哥题刷的不赖啊
fb电话面试分享A公司面经

 1 (共1页)
j*****g

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).

correct or not)，不知道各位大侠有什么高招?
d**e

2

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

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

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

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

6

n = strlen(str)
m = strlen(pattern) if pattern has no *, else n
j*****g

7
Hm...看着像suffix tree. 研究研究.....
s*****s

8

j*****g

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

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是什么？

i**********e

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

12
hm...
1. counter example: str=a, pattern=.
2. counter example: str=aac, pattern=*ac
d******a

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

14
What company is that? :-)

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

i**********e

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

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

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

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

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

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

i**********e

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

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[*] and mtch[*] 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[*] and mtch[*] to false
// mtch is true
mtch = new boolean[cstr.length + 1][];
for (int i = 0; i <= cstr.length; i++) {
mtch[i] = new boolean[cpatt.length + 1];
}
mtch = true;
if (cpatt.length > 0 && cpatt == '*')
mtch = 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

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 is true
mtch2 = new boolean[cpatt.length + 1];
mtch2 = true;
if (cpatt.length > 0 && cpatt == '*')
mtch2 = 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

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

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 is true
mtch2 = new boolean[cpatt.length + 1];
mtch2 = 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 = 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

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

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

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

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

30

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 *.

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的情况:

str1*str2*str3*str4,

P********l

31

【在 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

32
Agree.
Just felt this approach is fairly *simple and easy to remember*. So sharing
my thoughts here.
c***2

33
Here's my program, please help check whether I miss anything.
c***2

34
Here's my program, please help check whether I miss anything.
j*****g

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

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

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

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

39

j*****g

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页)

bloomberg onsite & offeronsite遇到的几个面试题

Facebook phone screenImplement strStr() ？