m*t
2 楼
嗯，下个月的够了。
G*r
3 楼
1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
的地方。这是找到的 Morels：
2. 清洗了的一部分。
3 找到的一颗大的
4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
disease的那种。很是恶心。
5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
6. 你能看见吗？
7. 漂亮的 Morel
8. Another One
9. 森林照片
10. 一对 Morels
11。 Big one
12. Morel 在哪儿？
13. 在这儿：
昨晚 Morel 炒肉吃了。Delicious。那味道颗真鲜。今天我还活着能 Post。 说明没有
毒。
哈哈。
好啦。Morel 的季节很短。今天还准备去找找。天亮了。准备出发了。回来再聊，回答
问题。
的地方。这是找到的 Morels：
2. 清洗了的一部分。
3 找到的一颗大的
4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
disease的那种。很是恶心。
5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
6. 你能看见吗？
7. 漂亮的 Morel
8. Another One
9. 森林照片
10. 一对 Morels
11。 Big one
12. Morel 在哪儿？
13. 在这儿：
昨晚 Morel 炒肉吃了。Delicious。那味道颗真鲜。今天我还活着能 Post。 说明没有
毒。
哈哈。
好啦。Morel 的季节很短。今天还准备去找找。天亮了。准备出发了。回来再聊，回答
问题。
b*u
4 楼
记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
C*g
5 楼
same here in VA
m*2
6 楼
Wow, 大赞！黑色跟黄色吃起来味道有区别吗？
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
b*m
7 楼
嗯，我思路类似，但是白板上写有些乱套……
【在 b*****u 的大作中提到】
: 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
l*d
8 楼
太诱人了，今年我一直找不到，决定今天再去找！
b*m
9 楼
大牛们给评价一下我下面的code，匆匆写的，没用太多case验证：
bool IsStringMatch(char *pattern, char *string)
{
if( !pattern || !string ) return false;
char *laststar = NULL;
while( *pattern && *string )
{
if( *pattern == '*' )
laststar = pattern;
else
{
if( *pattern != *string && *pattern != '?' )
{
if( laststar )
pattern = laststar;
else
return false;
}
}
pattern++;
string++;
}
if( *pattern || *string )
return false;
else
return true;
}
bool IsStringMatch(char *pattern, char *string)
{
if( !pattern || !string ) return false;
char *laststar = NULL;
while( *pattern && *string )
{
if( *pattern == '*' )
laststar = pattern;
else
{
if( *pattern != *string && *pattern != '?' )
{
if( laststar )
pattern = laststar;
else
return false;
}
}
pattern++;
string++;
}
if( *pattern || *string )
return false;
else
return true;
}
p*8
10 楼
太厉害了，知识就是美食
p*2
11 楼
你这个过了OJ了吗？我写了一下，不太好写呀。
【在 b***m 的大作中提到】
: 大牛们给评价一下我下面的code，匆匆写的，没用太多case验证：
: bool IsStringMatch(char *pattern, char *string)
: {
: if( !pattern || !string ) return false;
:
: char *laststar = NULL;
:
: while( *pattern && *string )
: {
: if( *pattern == '*' )
o*n
12 楼
心动不如行动，明天早上去树林里找找
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
b*m
13 楼
没试过OJ，用两个简单的case试了一下，好像没问题。
想写完美确实不容易，不过面试白板写题，也不是很容易写完美。
【在 p*****2 的大作中提到】
:
: 你这个过了OJ了吗？我写了一下，不太好写呀。
x*8
14 楼
采蘑菇的大兄弟，背着一只大罗筐，手里举着小手机呀，边找蘑菇边照相，啦啦啦 ...
哈哈
哈哈
h*n
15 楼
leetcode大牛前面写过一篇文章，貌似O（n）是不可能的
http://www.mitbbs.com/article_t/JobHunting/31715957.html
【在 b*****u 的大作中提到】
: 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
http://www.mitbbs.com/article_t/JobHunting/31715957.html
【在 b*****u 的大作中提到】
: 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
o*n
16 楼
太欢乐了，太应景了
..
【在 x**8 的大作中提到】
: 采蘑菇的大兄弟，背着一只大罗筐，手里举着小手机呀，边找蘑菇边照相，啦啦啦 ...
: 哈哈
..
【在 x**8 的大作中提到】
: 采蘑菇的大兄弟，背着一只大罗筐，手里举着小手机呀，边找蘑菇边照相，啦啦啦 ...
: 哈哈
h*n
17 楼
下面这些过不了
"aa", "*"
"", "*"
"a", "a*"
"a", "?*"
"ab", "*ab"
"mississippi", "m*si*"
"mississippi", "m*iss*"
"mississippi", "m*iss*iss*"
【在 b***m 的大作中提到】
: 大牛们给评价一下我下面的code，匆匆写的，没用太多case验证：
: bool IsStringMatch(char *pattern, char *string)
: {
: if( !pattern || !string ) return false;
:
: char *laststar = NULL;
:
: while( *pattern && *string )
: {
: if( *pattern == '*' )
"aa", "*"
"", "*"
"a", "a*"
"a", "?*"
"ab", "*ab"
"mississippi", "m*si*"
"mississippi", "m*iss*"
"mississippi", "m*iss*iss*"
【在 b***m 的大作中提到】
: 大牛们给评价一下我下面的code，匆匆写的，没用太多case验证：
: bool IsStringMatch(char *pattern, char *string)
: {
: if( !pattern || !string ) return false;
:
: char *laststar = NULL;
:
: while( *pattern && *string )
: {
: if( *pattern == '*' )
x*8
18 楼
还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
【在 o*******n 的大作中提到】
: 太欢乐了，太应景了
:
: ..
【在 o*******n 的大作中提到】
: 太欢乐了，太应景了
:
: ..
p*2
19 楼
我觉得这题面试最好还是用DP来解。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
boolean[][] dp=new boolean[2][n+1];
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
Arrays.fill(dp[i%2], false);
if(p.charAt(i)=='*')
for(int j=n;j>=0;j--)
{
if(dp[(i+1)%2][j])
for(int k=0;k<=j;k++)
dp[i%2][k]=true;
}
else
for(int j=n-1;j>=0;j--)
dp[i%2][j]=(p.charAt(i)==s.charAt(j) || p.charAt(i)=='?'
) && dp[(i+1)%2][j+1];
}
return dp[0][0];
}
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
boolean[][] dp=new boolean[2][n+1];
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
Arrays.fill(dp[i%2], false);
if(p.charAt(i)=='*')
for(int j=n;j>=0;j--)
{
if(dp[(i+1)%2][j])
for(int k=0;k<=j;k++)
dp[i%2][k]=true;
}
else
for(int j=n-1;j>=0;j--)
dp[i%2][j]=(p.charAt(i)==s.charAt(j) || p.charAt(i)=='?'
) && dp[(i+1)%2][j+1];
}
return dp[0][0];
}
o*n
20 楼
你和快乐宝宝可以联合说相声了
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
h*n
21 楼
貌似复杂度n^3了？
【在 p*****2 的大作中提到】
: 我觉得这题面试最好还是用DP来解。
: public boolean isMatch(String s, String p)
: {
: int n=s.length();
: int m=p.length();
:
: boolean[][] dp=new boolean[2][n+1];
: dp[m%2][n]=true;
:
: for(int i=m-1;i>=0;i--)
【在 p*****2 的大作中提到】
: 我觉得这题面试最好还是用DP来解。
: public boolean isMatch(String s, String p)
: {
: int n=s.length();
: int m=p.length();
:
: boolean[][] dp=new boolean[2][n+1];
: dp[m%2][n]=true;
:
: for(int i=m-1;i>=0;i--)
h*y
22 楼
哈哈!对咱们领导顿时由粉转痴! 总算跟对人了。那个谁谁，老是拿个相机照啥啥啥，
还老是幻想着去帮主家帮助落后铝同学，和咱领导的才气境界没法比。嘿嘿。
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，
嘿嘿
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
还老是幻想着去帮主家帮助落后铝同学，和咱领导的才气境界没法比。嘿嘿。
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，
嘿嘿
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
p*2
23 楼
n^2
【在 h****n 的大作中提到】
: 貌似复杂度n^3了？
x*8
24 楼
哈哈，俺是赶不上你和快乐宝贝的高水平滴。。。
你的那出going 395才是上得了台面的杰作。俺这个最多在幼儿园大班里流传。呵呵
【在 o*******n 的大作中提到】
: 你和快乐宝宝可以联合说相声了
你的那出going 395才是上得了台面的杰作。俺这个最多在幼儿园大班里流传。呵呵
【在 o*******n 的大作中提到】
: 你和快乐宝宝可以联合说相声了
h*n
25 楼
三个for套一起了，最坏情况下会是n^3吧？
【在 p*****2 的大作中提到】
:
: n^2
【在 p*****2 的大作中提到】
:
: n^2
x*8
26 楼
不敢当啊，不敢当。俺也就是读了大兄弟的帖子，然后从头到尾换了一下歌词，发现竟
然还合用。哈哈
这世上本来就是美眉慕才子，才子逐佳人。不怪，不怪...呵呵
如你所言属实，咱帮主喜欢清修，这样一来也是帮了帮主的大忙，不是坏事，不是坏事
... LOL
这楼好像歪得有点儿厉害哦 ：）
【在 h*******y 的大作中提到】
: 哈哈!对咱们领导顿时由粉转痴! 总算跟对人了。那个谁谁，老是拿个相机照啥啥啥，
: 还老是幻想着去帮主家帮助落后铝同学，和咱领导的才气境界没法比。嘿嘿。
:
:
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，
: 嘿嘿
:
然还合用。哈哈
这世上本来就是美眉慕才子，才子逐佳人。不怪，不怪...呵呵
如你所言属实，咱帮主喜欢清修，这样一来也是帮了帮主的大忙，不是坏事，不是坏事
... LOL
这楼好像歪得有点儿厉害哦 ：）
【在 h*******y 的大作中提到】
: 哈哈!对咱们领导顿时由粉转痴! 总算跟对人了。那个谁谁，老是拿个相机照啥啥啥，
: 还老是幻想着去帮主家帮助落后铝同学，和咱领导的才气境界没法比。嘿嘿。
:
:
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，
: 嘿嘿
:
p*2
27 楼
你再仔细看看。不过我可以换一种写法就更清楚了。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
boolean[][] dp=new boolean[2][n+1];
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
Arrays.fill(dp[i%2], false);
dp[i%2][n]=p.charAt(i)=='*' && dp[(i+1)%2][n];
for(int j=n-1;j>=0;j--)
if(p.charAt(i)=='*')
dp[i%2][j]=dp[(i+1)%2][j] || dp[i%2][j+1];
else
dp[i%2][j]=(p.charAt(i)==s.charAt(j) || p.charAt(i)=='?'
) && dp[(i+1)%2][j+1];
}
return dp[0][0];
}
【在 h****n 的大作中提到】
: 三个for套一起了，最坏情况下会是n^3吧？
w*e
28 楼
太赞了！羡慕！您在什么地区？我们这儿还早。
b*m
29 楼
嗯，是的，多谢，我再好好改改。这个题想写好真是不容易，我看到一个很好的代码，
是我的好几倍长。
【在 h****n 的大作中提到】
: 下面这些过不了
: "aa", "*"
: "", "*"
: "a", "a*"
: "a", "?*"
: "ab", "*ab"
: "mississippi", "m*si*"
:
: "mississippi", "m*iss*"
:
是我的好几倍长。
【在 h****n 的大作中提到】
: 下面这些过不了
: "aa", "*"
: "", "*"
: "a", "a*"
: "a", "?*"
: "ab", "*ab"
: "mississippi", "m*si*"
:
: "mississippi", "m*iss*"
:
l*d
30 楼
湖人真是贵人，今天到树林里去居然找着了morel。不多，只有七个，很满足了，呵呵
i*e
31 楼
longway2008 贴过的代码，估计是我看过非递归解法最短的行数了。。。但不好消化
bool isMatch(const char *str, const char *pat, bool hasStar=false)
{
if (!*pat) return !*str || hasStar;
const char *s, *p;
for (s = str, p = pat; *s; ++s, ++p) {
if (*p == '*')
return isMatch(s, p+1, true);
else if ( *p != '?' && *s != *p)
return !hasStar ? false : isMatch(str+1, pat, hasStar);
}
while (*p == '*') ++p;
return (!*p);
}
bool isMatch(const char *str, const char *pat, bool hasStar=false)
{
if (!*pat) return !*str || hasStar;
const char *s, *p;
for (s = str, p = pat; *s; ++s, ++p) {
if (*p == '*')
return isMatch(s, p+1, true);
else if ( *p != '?' && *s != *p)
return !hasStar ? false : isMatch(str+1, pat, hasStar);
}
while (*p == '*') ++p;
return (!*p);
}
L*9
32 楼
就知道馋我们
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
【在 G********r 的大作中提到】
: 1. 第一次在这里去 Morel Morel hunting。 周六同 J 一块开车1小时去他以前采摘过
: 的地方。这是找到的 Morels：
: 2. 清洗了的一部分。
: 3 找到的一颗大的
: 4. 觉得脖子上有什么东西再爬。用手抓来一看。是一个 Deer Tick。 就是携带Lime
: disease的那种。很是恶心。
: 5. 走进树林不到3分钟发现了我的第一个Yellow Morel：
: 6. 你能看见吗？
: 7. 漂亮的 Morel
: 8. Another One
p*2
33 楼
这个不是递归吗？
【在 i**********e 的大作中提到】
: longway2008 贴过的代码，估计是我看过非递归解法最短的行数了。。。但不好消化
: bool isMatch(const char *str, const char *pat, bool hasStar=false)
: {
: if (!*pat) return !*str || hasStar;
:
: const char *s, *p;
: for (s = str, p = pat; *s; ++s, ++p) {
: if (*p == '*')
: return isMatch(s, p+1, true);
: else if ( *p != '?' && *s != *p)
G*r
34 楼
四月30号 Morel Hunting：
今天收获不多， 20来颗。主要是不熟悉地形和植被。瞎闯。瞎猫碰着死老鼠呗。在树
林里走沿着很陡的坡上上下下。喝了几乎一加仑的水。
熊不少哦。有警告。还有新鲜的熊的排泄物。不过黑熊不可怕。一个人能对付一只熊。
我有一把Machete。
不知道是什么蝴蝶。很漂亮。
今天收获不多， 20来颗。主要是不熟悉地形和植被。瞎闯。瞎猫碰着死老鼠呗。在树
林里走沿着很陡的坡上上下下。喝了几乎一加仑的水。
熊不少哦。有警告。还有新鲜的熊的排泄物。不过黑熊不可怕。一个人能对付一只熊。
我有一把Machete。
不知道是什么蝴蝶。很漂亮。
i*e
35 楼
orz.. 哈哈，搞糊涂了。
这个非递归还是不好写，面试时写递归的已经很好了。
【在 p*****2 的大作中提到】
:
: 这个不是递归吗？
这个非递归还是不好写，面试时写递归的已经很好了。
【在 p*****2 的大作中提到】
:
: 这个不是递归吗？
G*r
36 楼
我觉得差别不大。有的人说黑的好吃些。可能黑的 Morel 长出来比黄的要早。就像吃
饺子一样，第一个饺子吃起来是最好吃的。
【在 m******2 的大作中提到】
: Wow, 大赞！黑色跟黄色吃起来味道有区别吗？
饺子一样，第一个饺子吃起来是最好吃的。
【在 m******2 的大作中提到】
: Wow, 大赞！黑色跟黄色吃起来味道有区别吗？
h*n
37 楼
我的递归版本
bool isMatch(const char *s, const char *p) {
if(*s=='\0')
{
if(*p=='\0') return true;
while(*p)
{
if(*p!='*') return false;
p++;
}
return true;
}
if(*p=='*') return isMatch(s+1,p) || isMatch(s,p+1);
else return (*p=='?'||*p==*s)?isMatch(s+1,p+1):false;
}
【在 i**********e 的大作中提到】
: longway2008 贴过的代码，估计是我看过非递归解法最短的行数了。。。但不好消化
: bool isMatch(const char *str, const char *pat, bool hasStar=false)
: {
: if (!*pat) return !*str || hasStar;
:
: const char *s, *p;
: for (s = str, p = pat; *s; ++s, ++p) {
: if (*p == '*')
: return isMatch(s, p+1, true);
: else if ( *p != '?' && *s != *p)
bool isMatch(const char *s, const char *p) {
if(*s=='\0')
{
if(*p=='\0') return true;
while(*p)
{
if(*p!='*') return false;
p++;
}
return true;
}
if(*p=='*') return isMatch(s+1,p) || isMatch(s,p+1);
else return (*p=='?'||*p==*s)?isMatch(s+1,p+1):false;
}
【在 i**********e 的大作中提到】
: longway2008 贴过的代码，估计是我看过非递归解法最短的行数了。。。但不好消化
: bool isMatch(const char *str, const char *pat, bool hasStar=false)
: {
: if (!*pat) return !*str || hasStar;
:
: const char *s, *p;
: for (s = str, p = pat; *s; ++s, ++p) {
: if (*p == '*')
: return isMatch(s, p+1, true);
: else if ( *p != '?' && *s != *p)
G*r
38 楼
Morel 非常奇怪。有的就在后院就有。就像前两天另一位就在自家的后院里发现了很多
。Morel只能在野外生长。到现在还没有人工栽培成功。因为Morel太特别了。它要同有
几种树共生的。他只长在这几种树下，
所以你要找到 Morel。 你一登要会识别树。我现在着这的就长在Poplar 树下。树越大
能长Morel的机会更大。你可以搜查一下 Morel 分布地图。
【在 l*****d 的大作中提到】
: 太诱人了，今年我一直找不到，决定今天再去找！
。Morel只能在野外生长。到现在还没有人工栽培成功。因为Morel太特别了。它要同有
几种树共生的。他只长在这几种树下，
所以你要找到 Morel。 你一登要会识别树。我现在着这的就长在Poplar 树下。树越大
能长Morel的机会更大。你可以搜查一下 Morel 分布地图。
【在 l*****d 的大作中提到】
: 太诱人了，今年我一直找不到，决定今天再去找！
h*n
39 楼
Leetcode，貌似递归没法通过你的large test cases
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
G*r
40 楼
味道确实好。今年本地的一个报纸还登了一片Morel的文章呢。
【在 p********8 的大作中提到】
: 太厉害了，知识就是美食
【在 p********8 的大作中提到】
: 太厉害了，知识就是美食
i*e
41 楼
要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
虑。
DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
memory exceed 的。
【在 h****n 的大作中提到】
: Leetcode，貌似递归没法通过你的large test cases
虑。
DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
memory exceed 的。
【在 h****n 的大作中提到】
: Leetcode，貌似递归没法通过你的large test cases
G*r
42 楼
一定要知道什么树下长Morel。否则找不到的。
如果你附近有刚死两三年的 American Elm 树的话。你碰到了，很可能采到七八个到大
几十个。有一次我在一棵死了的American Elm下发现了一些还没长大的 Morel。 我想
等几天再再来收获。等我周六再去看的时候，已经被别人采走了。我数了一下有 70 多
个stumps。我好后悔啊。那就是采蘑菇的趣味。有时候你赢，有时候你输。
【在 o*******n 的大作中提到】
: 心动不如行动，明天早上去树林里找找
如果你附近有刚死两三年的 American Elm 树的话。你碰到了，很可能采到七八个到大
几十个。有一次我在一棵死了的American Elm下发现了一些还没长大的 Morel。 我想
等几天再再来收获。等我周六再去看的时候，已经被别人采走了。我数了一下有 70 多
个stumps。我好后悔啊。那就是采蘑菇的趣味。有时候你赢，有时候你输。
【在 o*******n 的大作中提到】
: 心动不如行动，明天早上去树林里找找
b*m
43 楼
今天面试的烙印明确不让写递归。
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
G*r
44 楼
你还别说，就像你说的那样。不过山高水险，杂草丛生。森林里面是没有路的。
..
【在 x**8 的大作中提到】
: 采蘑菇的大兄弟，背着一只大罗筐，手里举着小手机呀，边找蘑菇边照相，啦啦啦 ...
: 哈哈
..
【在 x**8 的大作中提到】
: 采蘑菇的大兄弟，背着一只大罗筐，手里举着小手机呀，边找蘑菇边照相，啦啦啦 ...
: 哈哈
p*2
45 楼
不是。我优化空间了。
【在 i**********e 的大作中提到】
: 要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
: 虑。
: DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
: limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
: memory exceed 的。
G*r
46 楼
那Tick是很可恶的。我买的长筒袜子。吧牛仔裤的裤脚放进袜子里面。穿长袖的没有扣
子的套衫，下端扎进牛寨库里面。戴上帽子。Tick 就没有什么机会找到皮肤了。昨天
那个Tick就是脖子痒痒用手一抓，嗨，就是那个Tick。
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
子的套衫，下端扎进牛寨库里面。戴上帽子。Tick 就没有什么机会找到皮肤了。昨天
那个Tick就是脖子痒痒用手一抓，嗨，就是那个Tick。
【在 x**8 的大作中提到】
: 还有一句“回到家来洗蘑菇呀，发现一只tick咬屁股上，啦啦啦",没好意思加，嘿嘿
p*2
47 楼
那你就用DP呀。
【在 b***m 的大作中提到】
: 今天面试的烙印明确不让写递归。
G*r
48 楼
我靠近东部偏南 Atlantic region。上周末是 peak season。 我不知道。错过了。
Morel 季节在西海岸 加州，Oregon，和 Washington。不一样。东部和中西部一般四月
到五月。
你问问local的人。会有找Morel的。他们不会share它们的 Morel holes。 但是他们会
共享到来的季节的。一般来说，American Elm 树的叶子有5分硬币大的时候，Poplar
树的叶子有松鼠脚掌大的时候。morel就有了。
【在 w*******e 的大作中提到】
: 太赞了！羡慕！您在什么地区？我们这儿还早。
Morel 季节在西海岸 加州，Oregon，和 Washington。不一样。东部和中西部一般四月
到五月。
你问问local的人。会有找Morel的。他们不会share它们的 Morel holes。 但是他们会
共享到来的季节的。一般来说，American Elm 树的叶子有5分硬币大的时候，Poplar
树的叶子有松鼠脚掌大的时候。morel就有了。
【在 w*******e 的大作中提到】
: 太赞了！羡慕！您在什么地区？我们这儿还早。
h*n
49 楼
回头研究一下二爷的DP
leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢
leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢
G*r
50 楼
祝贺。祝贺。挺漂亮的。建议一点。不要把Morel拔出来。要用一把小刀沿着根部上面
一点点割下来。把跟部留在地下。以后还会长蘑菇。
清洗Morel的时候可以用牙刷刷根部。注意清除掉泥土和 Bugs。
morel炒鸡肉，猪肉都好吃
【在 l*****d 的大作中提到】
: 湖人真是贵人，今天到树林里去居然找着了morel。不多，只有七个，很满足了，呵呵
一点点割下来。把跟部留在地下。以后还会长蘑菇。
清洗Morel的时候可以用牙刷刷根部。注意清除掉泥土和 Bugs。
morel炒鸡肉，猪肉都好吃
【在 l*****d 的大作中提到】
: 湖人真是贵人，今天到树林里去居然找着了morel。不多，只有七个，很满足了，呵呵
p*2
51 楼
看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
了。
【在 h****n 的大作中提到】
: 回头研究一下二爷的DP
: leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢
x*8
52 楼
恭喜！呵呵
【在 l*****d 的大作中提到】
: 湖人真是贵人，今天到树林里去居然找着了morel。不多，只有七个，很满足了，呵呵
【在 l*****d 的大作中提到】
: 湖人真是贵人，今天到树林里去居然找着了morel。不多，只有七个，很满足了，呵呵
i*e
53 楼
那为什么 TLE 呢？
难道是java不稳定？
我转成c++试一试。
【在 p*****2 的大作中提到】
:
: 看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
: 了。
难道是java不稳定？
我转成c++试一试。
【在 p*****2 的大作中提到】
:
: 看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
: 了。
x*8
54 楼
呵呵，那家伙很讨厌，钻进去了要拽出来还要费点儿功夫。：）
【在 G********r 的大作中提到】
: 那Tick是很可恶的。我买的长筒袜子。吧牛仔裤的裤脚放进袜子里面。穿长袖的没有扣
: 子的套衫，下端扎进牛寨库里面。戴上帽子。Tick 就没有什么机会找到皮肤了。昨天
: 那个Tick就是脖子痒痒用手一抓，嗨，就是那个Tick。
【在 G********r 的大作中提到】
: 那Tick是很可恶的。我买的长筒袜子。吧牛仔裤的裤脚放进袜子里面。穿长袖的没有扣
: 子的套衫，下端扎进牛寨库里面。戴上帽子。Tick 就没有什么机会找到皮肤了。昨天
: 那个Tick就是脖子痒痒用手一抓，嗨，就是那个Tick。
p*2
55 楼
时间是n*m, 空间是n
时间复杂度高所以会TLE
【在 i**********e 的大作中提到】
: 那为什么 TLE 呢？
: 难道是java不稳定？
: 我转成c++试一试。
G*r
56 楼
是的。晓得伤口不一定有Lime 病毒。但是伤口要好长时间才愈合。
【在 x**8 的大作中提到】
: 呵呵，那家伙很讨厌，钻进去了要拽出来还要费点儿功夫。：）
【在 x**8 的大作中提到】
: 呵呵，那家伙很讨厌，钻进去了要拽出来还要费点儿功夫。：）
l*a
57 楼
今天什么厂
看起来这个烙印还挺牛
【在 b***m 的大作中提到】
: 今天面试的烙印明确不让写递归。
看起来这个烙印还挺牛
【在 b***m 的大作中提到】
: 今天面试的烙印明确不让写递归。
y*2
58 楼
真不错！长知识：）
h*n
59 楼
试过了二爷的C++版本，还是超时了，谁贴个能通过OJ大test case的版本
bool isMatch(const char *s, const char *p)
{
int i,j;
int n=0,m=0;
const char* tmp;
tmp = s;
while(*tmp++)n++;
tmp = p;
while(*tmp++)m++;
vector > dp(2,vector(n+1, false));
dp[m%2][n] = true;
for(i=m-1;i>=0;i--)
{
dp[i%2].assign(n+1, false);
dp[i%2][n] = (p[i]=='*'&&dp[(i+1)%2][n]);
for(j=n-1;j>=0;j--)
if(p[i]=='*')
dp[i%2][j] = dp[(i+1)%2][j]||dp[i%2][j+1];
else
dp[i%2][j] = (p[i]==s[j]||p[i]=='?')
&&dp[(i+1)%2][j+1];
}
return dp[0][0];
}
bool isMatch(const char *s, const char *p)
{
int i,j;
int n=0,m=0;
const char* tmp;
tmp = s;
while(*tmp++)n++;
tmp = p;
while(*tmp++)m++;
vector
dp[m%2][n] = true;
for(i=m-1;i>=0;i--)
{
dp[i%2].assign(n+1, false);
dp[i%2][n] = (p[i]=='*'&&dp[(i+1)%2][n]);
for(j=n-1;j>=0;j--)
if(p[i]=='*')
dp[i%2][j] = dp[(i+1)%2][j]||dp[i%2][j+1];
else
dp[i%2][j] = (p[i]==s[j]||p[i]=='?')
&&dp[(i+1)%2][j+1];
}
return dp[0][0];
}
p*2
60 楼
同问。感觉面试官还挺猖
【在 l*****a 的大作中提到】
: 今天什么厂
: 看起来这个烙印还挺牛
b*m
61 楼
俺不会DP。二爷在西雅图地区吗？我请你吃饭，给我讲讲DP呗。
【在 p*****2 的大作中提到】
:
: 同问。感觉面试官还挺猖
【在 p*****2 的大作中提到】
:
: 同问。感觉面试官还挺猖
b*m
62 楼
M家呀，今天是个Senior Test Lead，做File Server的。
【在 l*****a 的大作中提到】
: 今天什么厂
: 看起来这个烙印还挺牛
【在 l*****a 的大作中提到】
: 今天什么厂
: 看起来这个烙印还挺牛
i*e
63 楼
你可以看看我这个是不是跟你一样的啊？
为什么large case 里错了两三个（除掉最后一个 TLE 的case 之外）？
bool isMatch(const char *s, const char *p) {
int n=strlen(s);
int m=strlen(p);
bool dp[2][n+1];
for (int i = 0; i < 1; i++) {
for (int j = 0; j < n+1; j++)
dp[i][j] = false;
}
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
for (int j=0;j
}
dp[i%2][n]=(p[i]=='*' && dp[(i+1)%2][n]);
for(int j=n-1;j>=0;j--)
if(p[i]=='*')
dp[i%2][j]=(dp[(i+1)%2][j] || dp[i%2][j+1]);
else
dp[i%2][j]=((p[i]==s[j] || p[i]=='?') && dp[(i+1)%2][j+1
]);
}
return dp[0][0];
}
PS: 这个DP不能过了，最后的test 是 m=32k, n=32k，所以 O(MN) 的算法都过不了了。
【在 h****n 的大作中提到】
: 试过了二爷的C++版本，还是超时了，谁贴个能通过OJ大test case的版本
: bool isMatch(const char *s, const char *p)
: {
: int i,j;
: int n=0,m=0;
: const char* tmp;
: tmp = s;
: while(*tmp++)n++;
: tmp = p;
: while(*tmp++)m++;
为什么large case 里错了两三个（除掉最后一个 TLE 的case 之外）？
bool isMatch(const char *s, const char *p) {
int n=strlen(s);
int m=strlen(p);
bool dp[2][n+1];
for (int i = 0; i < 1; i++) {
for (int j = 0; j < n+1; j++)
dp[i][j] = false;
}
dp[m%2][n]=true;
for(int i=m-1;i>=0;i--)
{
for (int j=0;j
}
dp[i%2][n]=(p[i]=='*' && dp[(i+1)%2][n]);
for(int j=n-1;j>=0;j--)
if(p[i]=='*')
dp[i%2][j]=(dp[(i+1)%2][j] || dp[i%2][j+1]);
else
dp[i%2][j]=((p[i]==s[j] || p[i]=='?') && dp[(i+1)%2][j+1
]);
}
return dp[0][0];
}
PS: 这个DP不能过了，最后的test 是 m=32k, n=32k，所以 O(MN) 的算法都过不了了。
【在 h****n 的大作中提到】
: 试过了二爷的C++版本，还是超时了，谁贴个能通过OJ大test case的版本
: bool isMatch(const char *s, const char *p)
: {
: int i,j;
: int n=0,m=0;
: const char* tmp;
: tmp = s;
: while(*tmp++)n++;
: tmp = p;
: while(*tmp++)m++;
h*n
64 楼
额，一旦出现TLE我这里没法显示之前通过或者没通过的那些cases。。试了几个浏览器
都不行
【在 i**********e 的大作中提到】
: 你可以看看我这个是不是跟你一样的啊？
: 为什么large case 里错了两三个（除掉最后一个 TLE 的case 之外）？
: bool isMatch(const char *s, const char *p) {
: int n=strlen(s);
: int m=strlen(p);
: bool dp[2][n+1];
: for (int i = 0; i < 1; i++) {
: for (int j = 0; j < n+1; j++)
: dp[i][j] = false;
: }
都不行
【在 i**********e 的大作中提到】
: 你可以看看我这个是不是跟你一样的啊？
: 为什么large case 里错了两三个（除掉最后一个 TLE 的case 之外）？
: bool isMatch(const char *s, const char *p) {
: int n=strlen(s);
: int m=strlen(p);
: bool dp[2][n+1];
: for (int i = 0; i < 1; i++) {
: for (int j = 0; j < n+1; j++)
: dp[i][j] = false;
: }
p*2
65 楼
是那个长的不错的烙印吗？
【在 b***m 的大作中提到】
: M家呀，今天是个Senior Test Lead，做File Server的。
p*2
66 楼
你能不能run一下我的程序呀？
【在 i**********e 的大作中提到】
: 你可以看看我这个是不是跟你一样的啊？
: 为什么large case 里错了两三个（除掉最后一个 TLE 的case 之外）？
: bool isMatch(const char *s, const char *p) {
: int n=strlen(s);
: int m=strlen(p);
: bool dp[2][n+1];
: for (int i = 0; i < 1; i++) {
: for (int j = 0; j < n+1; j++)
: dp[i][j] = false;
: }
i*e
67 楼
你现在再试一试好吗？
我暂时把那个最大的large case去除掉了。
【在 h****n 的大作中提到】
: 额，一旦出现TLE我这里没法显示之前通过或者没通过的那些cases。。试了几个浏览器
: 都不行
我暂时把那个最大的large case去除掉了。
【在 h****n 的大作中提到】
: 额，一旦出现TLE我这里没法显示之前通过或者没通过的那些cases。。试了几个浏览器
: 都不行
i*e
68 楼
run 了啊。
java 除了那个最大的case之外，全都过了。
但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
有问题。能帮我看看吗？
【在 p*****2 的大作中提到】
:
: 你能不能run一下我的程序呀？
java 除了那个最大的case之外，全都过了。
但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
有问题。能帮我看看吗？
【在 p*****2 的大作中提到】
:
: 你能不能run一下我的程序呀？
p*2
69 楼
DP一顿饭估计也讲不清楚，不过这题的应该能讲明白。你住哪里？
【在 b***m 的大作中提到】
: 俺不会DP。二爷在西雅图地区吗？我请你吃饭，给我讲讲DP呗。
p*2
70 楼
我看一下。
【在 i**********e 的大作中提到】
: run 了啊。
: java 除了那个最大的case之外，全都过了。
: 但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
: 有问题。能帮我看看吗？
p*2
71 楼
其实就是个低级错误
for (int i = 0; i < 1; i++)
【在 i**********e 的大作中提到】
: run 了啊。
: java 除了那个最大的case之外，全都过了。
: 但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
: 有问题。能帮我看看吗？
i*e
72 楼
啊，对。难怪，谢谢啊。
【在 p*****2 的大作中提到】
:
: 其实就是个低级错误
: for (int i = 0; i < 1; i++)
【在 p*****2 的大作中提到】
:
: 其实就是个低级错误
: for (int i = 0; i < 1; i++)
p*2
73 楼
不过感觉C＋＋写起来还是比Java罗嗦一些。不过C＋＋有指针，有些题就做的很灵活，
简洁。
简洁。
p*2
74 楼
呵呵。这东西自己看最难了。
【在 i**********e 的大作中提到】
: 啊，对。难怪，谢谢啊。
b*m
75 楼
啊？你怎么知道？是长得还不错。口音不算重。
【在 p*****2 的大作中提到】
:
: 呵呵。这东西自己看最难了。
b*m
76 楼
吃饭归吃饭，吃饭讲不清楚，吃完饭继续讲呀。我住Kirkland，平常就在Main Campus
周边转悠。
【在 p*****2 的大作中提到】
:
: 呵呵。这东西自己看最难了。
p*2
77 楼
貌似以前面过我。我没做出来，不过最后还是给了我onsite了。
【在 b***m 的大作中提到】
:
: 吃饭归吃饭，吃饭讲不清楚，吃完饭继续讲呀。我住Kirkland，平常就在Main Campus
: 周边转悠。
b*m
78 楼
给你发站内邮件了哦。
p*2
79 楼
回了。
【在 b***m 的大作中提到】
: 给你发站内邮件了哦。
l*a
80 楼
p*2
81 楼
感觉挺麻烦呀。
【在 l*****a 的大作中提到】
: 这里有个非递归的。
: http://blog.csdn.net/hopeztm/article/details/8039777
b*m
82 楼
这个想写好还真不容易，看来我今天做题也不算太差。
l*8
83 楼
刚才写了这个，通过了leetcode大数据量测试
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) {
if (!star) {
return false;
} else {
p = star+1;
s = ++s_save;
}
} else {
s++;
p++;
}
}
while (*p == '*') p++;
return !*p;
}
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) {
if (!star) {
return false;
} else {
p = star+1;
s = ++s_save;
}
} else {
s++;
p++;
}
}
while (*p == '*') p++;
return !*p;
}
p*2
84 楼
真简洁。膜拜一个。
【在 l*********8 的大作中提到】
: 刚才写了这个，通过了leetcode大数据量测试
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) {
: if (!star) {
p*2
85 楼
longway，你写这个大概花了多少时间呀？
【在 l*********8 的大作中提到】
: 刚才写了这个，通过了leetcode大数据量测试
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) {
: if (!star) {
l*8
86 楼
不敢当，我刚才写的时候，开始也挺晕的，要是刚才是面试就挂在白板上了。
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
b*m
87 楼
能简单总结一下思想吗？
【在 l*********8 的大作中提到】
: 刚才写了这个，通过了leetcode大数据量测试
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) {
: if (!star) {
l*8
88 楼
哎，刚才花了45分钟才写对吧。。。面试就挂了。
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
h*n
89 楼
赞，保存下来学习
【在 l*********8 的大作中提到】
: 刚才写了这个，通过了leetcode大数据量测试
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) {
: if (!star) {
【在 l*********8 的大作中提到】
: 刚才写了这个，通过了leetcode大数据量测试
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) {
: if (!star) {
l*8
90 楼
我加了注释
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
// star是上一个*出现的位置；s_save+1是出现不匹配时，s应该回到的位置。
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) { // 不匹配
if (!star) { // 没有*来做灵活匹配
return false;
} else { // 有*， 回到star+1 和 s_save+1匹配
p = star+1;
s = ++s_save;
}
} else { // 匹配时，p和s都前进到下一个
s++;
p++;
}
}
while (*p == '*') p++; // pattern结尾的*可以消耗掉
return !*p; // 看是否已经到p的末尾
}
【在 b***m 的大作中提到】
:
: 能简单总结一下思想吗？
bool isMatch(const char *s, const char *p) {
if (!p) return !s;
if (!s) return !p;
for (const char *star=NULL, *s_save=s; *s; ) {
// star是上一个*出现的位置；s_save+1是出现不匹配时，s应该回到的位置。
if (*p == '*') {
star = p++;
s_save = s;
} else if ( *p != '?' && *s != *p) { // 不匹配
if (!star) { // 没有*来做灵活匹配
return false;
} else { // 有*， 回到star+1 和 s_save+1匹配
p = star+1;
s = ++s_save;
}
} else { // 匹配时，p和s都前进到下一个
s++;
p++;
}
}
while (*p == '*') p++; // pattern结尾的*可以消耗掉
return !*p; // 看是否已经到p的末尾
}
【在 b***m 的大作中提到】
:
: 能简单总结一下思想吗？
p*2
91 楼
很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
，就改DP了。不过这东西我感觉面试真不容易写的bug free。
【在 l*********8 的大作中提到】
: 哎，刚才花了45分钟才写对吧。。。面试就挂了。
b*m
92 楼
多谢！核心语句其实就是这句：
if (!star) { // 没有*来做灵活匹配
return false;
} else { // 有*， 回到star+1 和 s_save+1匹配
p = star+1;
s = ++s_save;
}
一旦不匹配又有过往的*，那么就把p回溯到上个*的下一个字符，把s回溯到p出现*时s
对应的下一个字符，对吗？
【在 l*********8 的大作中提到】
: 我加了注释
: bool isMatch(const char *s, const char *p) {
: if (!p) return !s;
: if (!s) return !p;
: for (const char *star=NULL, *s_save=s; *s; ) {
: // star是上一个*出现的位置；s_save+1是出现不匹配时，s应该回到的位置。
: if (*p == '*') {
: star = p++;
: s_save = s;
: } else if ( *p != '?' && *s != *p) { // 不匹配
l*8
93 楼
差不多，不过不仅仅是“把s回溯到p出现*时s对应的下一个字符”。 一直不能匹配的
时候，s_save也一直增加，就跟简单字符串匹配差不多。
s
【在 b***m 的大作中提到】
:
: 多谢！核心语句其实就是这句：
: if (!star) { // 没有*来做灵活匹配
: return false;
: } else { // 有*， 回到star+1 和 s_save+1匹配
: p = star+1;
: s = ++s_save;
: }
: 一旦不匹配又有过往的*，那么就把p回溯到上个*的下一个字符，把s回溯到p出现*时s
: 对应的下一个字符，对吗？
时候，s_save也一直增加，就跟简单字符串匹配差不多。
s
【在 b***m 的大作中提到】
:
: 多谢！核心语句其实就是这句：
: if (!star) { // 没有*来做灵活匹配
: return false;
: } else { // 有*， 回到star+1 和 s_save+1匹配
: p = star+1;
: s = ++s_save;
: }
: 一旦不匹配又有过往的*，那么就把p回溯到上个*的下一个字符，把s回溯到p出现*时s
: 对应的下一个字符，对吗？
l*8
94 楼
恩，这个题没好好写过的话，面试真不容易写。 我第一次写了通过OJ的时候，好像写
了六七十行。。。。。
【在 p*****2 的大作中提到】
:
: 很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
: ，就改DP了。不过这东西我感觉面试真不容易写的bug free。
了六七十行。。。。。
【在 p*****2 的大作中提到】
:
: 很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
: ，就改DP了。不过这东西我感觉面试真不容易写的bug free。
b*m
95 楼
就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？
【在 l*********8 的大作中提到】
: 差不多，不过不仅仅是“把s回溯到p出现*时s对应的下一个字符”。 一直不能匹配的
: 时候，s_save也一直增加，就跟简单字符串匹配差不多。
:
: s
【在 l*********8 的大作中提到】
: 差不多，不过不仅仅是“把s回溯到p出现*时s对应的下一个字符”。 一直不能匹配的
: 时候，s_save也一直增加，就跟简单字符串匹配差不多。
:
: s
p*2
96 楼
我用Java写了一个，真是没有C＋＋简洁呀。
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
int i=0;
int j=0;
int star=-1;
int sp=0;
while(i
//one * and multiple *, same effect
while(j
star=j++; //* match 0 character
sp=i;
}
if(j==m || (p.charAt(j)!=s.charAt(i) && p.charAt(j)!='?'))
{
if(star<0)
return false;
else
{
j=star+1;
i=++sp; //* match 1 character
}
}
else
{
i++;
j++;
}
}
while(j
}
public boolean isMatch(String s, String p)
{
int n=s.length();
int m=p.length();
int i=0;
int j=0;
int star=-1;
int sp=0;
while(i
//one * and multiple *, same effect
while(j
star=j++; //* match 0 character
sp=i;
}
if(j==m || (p.charAt(j)!=s.charAt(i) && p.charAt(j)!='?'))
{
if(star<0)
return false;
else
{
j=star+1;
i=++sp; //* match 1 character
}
}
else
{
i++;
j++;
}
}
while(j
}
l*8
97 楼
恩，差不多是这个意思
【在 b***m 的大作中提到】
: 就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？
【在 b***m 的大作中提到】
: 就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？
b*m
98 楼
想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？
【在 l*********8 的大作中提到】
: 恩，差不多是这个意思
h*n
99 楼
应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？
【在 b***m 的大作中提到】
:
: 想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？
【在 b***m 的大作中提到】
:
: 想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？
b*m
100 楼
嗯，应该是n^2。
【在 h****n 的大作中提到】
: 应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？
【在 h****n 的大作中提到】
: 应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？
相关阅读