b***m
发帖数: 5987 | |
b*****u
发帖数: 648 | 2 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n) |
b***m
发帖数: 5987 | 3
嗯，我思路类似，但是白板上写有些乱套……
【在 b*****u 的大作中提到】
: 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
|
b***m
发帖数: 5987 | 4 大牛们给评价一下我下面的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;
} |
p*****2
发帖数: 21240 | 5
你这个过了OJ了吗？我写了一下，不太好写呀。
【在 b***m 的大作中提到】
: 大牛们给评价一下我下面的code，匆匆写的，没用太多case验证：
: bool IsStringMatch(char *pattern, char *string)
: {
: if( !pattern || !string ) return false;
:
: char *laststar = NULL;
:
: while( *pattern && *string )
: {
: if( *pattern == '*' )
|
b***m
发帖数: 5987 | 6
没试过OJ，用两个简单的case试了一下，好像没问题。
想写完美确实不容易，不过面试白板写题，也不是很容易写完美。
【在 p*****2 的大作中提到】
:
: 你这个过了OJ了吗？我写了一下，不太好写呀。
|
h****n
发帖数: 1093 | 7 leetcode大牛前面写过一篇文章，貌似O（n）是不可能的
http://www.mitbbs.com/article_t/JobHunting/31715957.html
【在 b*****u 的大作中提到】
: 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n)
|
h****n
发帖数: 1093 | 8 下面这些过不了
"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 == '*' )
|
p*****2
发帖数: 21240 | 9 我觉得这题面试最好还是用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];
} |
h****n
发帖数: 1093 | 10 貌似复杂度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
发帖数: 21240 | 11
n^2
【在 h****n 的大作中提到】
: 貌似复杂度n^3了？
|
h****n
发帖数: 1093 | 12 三个for套一起了，最坏情况下会是n^3吧？
【在 p*****2 的大作中提到】
:
: n^2
|
p*****2
发帖数: 21240 | 13
你再仔细看看。不过我可以换一种写法就更清楚了。
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吧？
|
b***m
发帖数: 5987 | 14 嗯，是的，多谢，我再好好改改。这个题想写好真是不容易，我看到一个很好的代码，
是我的好几倍长。
【在 h****n 的大作中提到】
: 下面这些过不了
: "aa", "*"
: "", "*"
: "a", "a*"
: "a", "?*"
: "ab", "*ab"
: "mississippi", "m*si*"
:
: "mississippi", "m*iss*"
:
|
i**********e
发帖数: 1145 | 15 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);
} |
p*****2
发帖数: 21240 | 16
这个不是递归吗？
【在 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)
|
i**********e
发帖数: 1145 | 17 orz.. 哈哈，搞糊涂了。
这个非递归还是不好写，面试时写递归的已经很好了。
【在 p*****2 的大作中提到】
:
: 这个不是递归吗？
|
h****n
发帖数: 1093 | 18 我的递归版本
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)
|
h****n
发帖数: 1093 | 19 Leetcode，貌似递归没法通过你的large test cases
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
|
i**********e
发帖数: 1145 | 20 要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
虑。
DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
memory exceed 的。
【在 h****n 的大作中提到】
: Leetcode，貌似递归没法通过你的large test cases
|
|
|
b***m
发帖数: 5987 | 21 今天面试的烙印明确不让写递归。
【在 i**********e 的大作中提到】
: orz.. 哈哈，搞糊涂了。
: 这个非递归还是不好写，面试时写递归的已经很好了。
|
p*****2
发帖数: 21240 | 22
不是。我优化空间了。
【在 i**********e 的大作中提到】
: 要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
: 虑。
: DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
: limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
: memory exceed 的。
|
p*****2
发帖数: 21240 | 23
那你就用DP呀。
【在 b***m 的大作中提到】
: 今天面试的烙印明确不让写递归。
|
h****n
发帖数: 1093 | 24 回头研究一下二爷的DP
leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢 |
p*****2
发帖数: 21240 | 25
看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
了。
【在 h****n 的大作中提到】
: 回头研究一下二爷的DP
: leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢
|
i**********e
发帖数: 1145 | 26 那为什么 TLE 呢？
难道是java不稳定？
我转成c++试一试。
【在 p*****2 的大作中提到】
:
: 看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
: 了。
|
p*****2
发帖数: 21240 | 27
时间是n*m, 空间是n
时间复杂度高所以会TLE
【在 i**********e 的大作中提到】
: 那为什么 TLE 呢？
: 难道是java不稳定？
: 我转成c++试一试。
|
l*****a
发帖数: 14598 | 28 今天什么厂
看起来这个烙印还挺牛
【在 b***m 的大作中提到】
: 今天面试的烙印明确不让写递归。
|
h****n
发帖数: 1093 | 29 试过了二爷的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];
} |
p*****2
发帖数: 21240 | 30
同问。感觉面试官还挺猖
【在 l*****a 的大作中提到】
: 今天什么厂
: 看起来这个烙印还挺牛
|
|
|
b***m
发帖数: 5987 | 31 俺不会DP。二爷在西雅图地区吗？我请你吃饭，给我讲讲DP呗。
【在 p*****2 的大作中提到】
:
: 同问。感觉面试官还挺猖
|
b***m
发帖数: 5987 | 32 M家呀，今天是个Senior Test Lead，做File Server的。
【在 l*****a 的大作中提到】
: 今天什么厂
: 看起来这个烙印还挺牛
|
i**********e
发帖数: 1145 | 33 你可以看看我这个是不是跟你一样的啊？
为什么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][j] = false;
}
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
发帖数: 1093 | 34 额，一旦出现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;
: }
|
p*****2
发帖数: 21240 | 35
是那个长的不错的烙印吗？
【在 b***m 的大作中提到】
: M家呀，今天是个Senior Test Lead，做File Server的。
|
p*****2
发帖数: 21240 | 36
你能不能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
发帖数: 1145 | 37 你现在再试一试好吗？
我暂时把那个最大的large case去除掉了。
【在 h****n 的大作中提到】
: 额，一旦出现TLE我这里没法显示之前通过或者没通过的那些cases。。试了几个浏览器
: 都不行
|
i**********e
发帖数: 1145 | 38 run 了啊。
java 除了那个最大的case之外，全都过了。
但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
有问题。能帮我看看吗？
【在 p*****2 的大作中提到】
:
: 你能不能run一下我的程序呀？
|
p*****2
发帖数: 21240 | 39
DP一顿饭估计也讲不清楚，不过这题的应该能讲明白。你住哪里？
【在 b***m 的大作中提到】
: 俺不会DP。二爷在西雅图地区吗？我请你吃饭，给我讲讲DP呗。
|
p*****2
发帖数: 21240 | 40
我看一下。
【在 i**********e 的大作中提到】
: run 了啊。
: java 除了那个最大的case之外，全都过了。
: 但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
: 有问题。能帮我看看吗？
|
|
|
p*****2
发帖数: 21240 | 41
其实就是个低级错误
for (int i = 0; i < 1; i++)
【在 i**********e 的大作中提到】
: run 了啊。
: java 除了那个最大的case之外，全都过了。
: 但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
: 有问题。能帮我看看吗？
|
i**********e
发帖数: 1145 | 42 啊，对。难怪，谢谢啊。
【在 p*****2 的大作中提到】
:
: 其实就是个低级错误
: for (int i = 0; i < 1; i++)
|
p*****2
发帖数: 21240 | 43 不过感觉C＋＋写起来还是比Java罗嗦一些。不过C＋＋有指针，有些题就做的很灵活，
简洁。 |
p*****2
发帖数: 21240 | 44
呵呵。这东西自己看最难了。
【在 i**********e 的大作中提到】
: 啊，对。难怪，谢谢啊。
|
b***m
发帖数: 5987 | 45
啊？你怎么知道？是长得还不错。口音不算重。
【在 p*****2 的大作中提到】
:
: 呵呵。这东西自己看最难了。
|
b***m
发帖数: 5987 | 46
吃饭归吃饭，吃饭讲不清楚，吃完饭继续讲呀。我住Kirkland，平常就在Main Campus
周边转悠。
【在 p*****2 的大作中提到】
:
: 呵呵。这东西自己看最难了。
|
p*****2
发帖数: 21240 | 47
貌似以前面过我。我没做出来，不过最后还是给了我onsite了。
【在 b***m 的大作中提到】
:
: 吃饭归吃饭，吃饭讲不清楚，吃完饭继续讲呀。我住Kirkland，平常就在Main Campus
: 周边转悠。
|
b***m
发帖数: 5987 | |
p*****2
发帖数: 21240 | 49
回了。
【在 b***m 的大作中提到】
: 给你发站内邮件了哦。
|
l*****a
发帖数: 559 | |
|
|
p*****2
发帖数: 21240 | |
b***m
发帖数: 5987 | 52 这个想写好还真不容易，看来我今天做题也不算太差。 |
l*********8
发帖数: 4642 | 53 刚才写了这个，通过了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;
} |
p*****2
发帖数: 21240 | 54
真简洁。膜拜一个。
【在 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
发帖数: 21240 | 55
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
发帖数: 4642 | 56 不敢当，我刚才写的时候，开始也挺晕的，要是刚才是面试就挂在白板上了。
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
|
b***m
发帖数: 5987 | 57
能简单总结一下思想吗？
【在 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
发帖数: 4642 | 58 哎，刚才花了45分钟才写对吧。。。面试就挂了。
【在 p*****2 的大作中提到】
:
: longway，你写这个大概花了多少时间呀？
|
h****n
发帖数: 1093 | 59 赞，保存下来学习
【在 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
发帖数: 4642 | 60 我加了注释
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
发帖数: 21240 | 61
很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
，就改DP了。不过这东西我感觉面试真不容易写的bug free。
【在 l*********8 的大作中提到】
: 哎，刚才花了45分钟才写对吧。。。面试就挂了。
|
b***m
发帖数: 5987 | 62
多谢！核心语句其实就是这句：
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
发帖数: 4642 | 63 差不多，不过不仅仅是“把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
发帖数: 4642 | 64 恩，这个题没好好写过的话，面试真不容易写。 我第一次写了通过OJ的时候，好像写
了六七十行。。。。。
【在 p*****2 的大作中提到】
:
: 很牛了。我刚才试着写了一下，最好的是过了80多个test case，调不通，感觉水很深
: ，就改DP了。不过这东西我感觉面试真不容易写的bug free。
|
b***m
发帖数: 5987 | 65 就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？
【在 l*********8 的大作中提到】
: 差不多，不过不仅仅是“把s回溯到p出现*时s对应的下一个字符”。 一直不能匹配的
: 时候，s_save也一直增加，就跟简单字符串匹配差不多。
:
: s
|
p*****2
发帖数: 21240 | 66 我用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
return j==m;
} |
l*********8
发帖数: 4642 | 67 恩，差不多是这个意思
【在 b***m 的大作中提到】
: 就是说一旦开始不匹配，就用那个*一点点地往后吃不匹配字符，直到又出现匹配？
|
b***m
发帖数: 5987 | 68
想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？
【在 l*********8 的大作中提到】
: 恩，差不多是这个意思
|
h****n
发帖数: 1093 | 69 应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？
【在 b***m 的大作中提到】
:
: 想法不错，代码也很整洁易懂，是O(n)时间复杂度吗？
|
b***m
发帖数: 5987 | 70 嗯，应该是n^2。
【在 h****n 的大作中提到】
: 应该不是O（n）有回溯了 最坏情况下应该也有n^2了貌似？
|
