C***U
发帖数: 2406 | 1 恩
谢谢指教
增加了一点信心 因为我现在很难写到bug free
一般都要调试才能改对 |
|
|
|
f*******4
发帖数: 64 | 4 记住上一次匹配到*的位置,下一次不匹配的时候用*消去.
不用DP |
|
|
|
|
m****v
发帖数: 84 | 8 请问这是greedy么？如果是，如何证明呢？
如果不是，能再详细点说一下算法么？
非常感谢！ |
|
f*******4
发帖数: 64 | 9 如果字符不匹配(也不是?),那就需要*来消.考虑 ..a*b..c*d..n..
假设在n处不匹配,如果用a之后的*来消去这次不匹配,而最终也匹配成功了,那么使用c
之后的*必然也能最终匹配成功;反过来则未必.
所以只要用最后一个*来过掉不匹配 |
|
|
p******9
发帖数: 47 | 11 这个算法复杂度是O(MN) 不是O(M + N) |
|
|
b*****u
发帖数: 648 | 13 记录此前最后一个*,如果当前不匹配了则用那个*覆盖到现在，这样总共是 O(n) |
|
|
b***m
发帖数: 5987 | 15 大牛们给评价一下我下面的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;
}
... 阅读全帖 |
|
p*****2
发帖数: 21240 | 16
你这个过了OJ了吗？我写了一下，不太好写呀。 |
|
b***m
发帖数: 5987 | 17
没试过OJ，用两个简单的case试了一下，好像没问题。
想写完美确实不容易，不过面试白板写题，也不是很容易写完美。 |
|
|
h****n
发帖数: 1093 | 19 下面这些过不了
"aa", "*"
"", "*"
"a", "a*"
"a", "?*"
"ab", "*ab"
"mississippi", "m*si*"
"mississippi", "m*iss*"
"mississippi", "m*iss*iss*" |
|
p*****2
发帖数: 21240 | 20 我觉得这题面试最好还是用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... 阅读全帖 |
|
|
|
|
p*****2
发帖数: 21240 | 24
你再仔细看看。不过我可以换一种写法就更清楚了。
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];
... 阅读全帖 |
|
b***m
发帖数: 5987 | 25 嗯，是的，多谢，我再好好改改。这个题想写好真是不容易，我看到一个很好的代码，
是我的好几倍长。 |
|
i**********e
发帖数: 1145 | 26 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);
} |
|
|
i**********e
发帖数: 1145 | 28 orz.. 哈哈，搞糊涂了。
这个非递归还是不好写，面试时写递归的已经很好了。 |
|
h****n
发帖数: 1093 | 29 我的递归版本
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;
} |
|
h****n
发帖数: 1093 | 30 Leetcode，貌似递归没法通过你的large test cases |
|
i**********e
发帖数: 1145 | 31 要通过large case 只能用非递归的。不过那个面试写太复杂了，很多edge case 要考
虑。
DP 的解法复杂度是 O(m*n) 一般都是 memory exceed，我不知道二爷的为什么 time
limit exceed。也有可能java 跑得慢的缘故吧。二爷的代码如果转换成C++应该是
memory exceed 的。 |
|
|
|
|
h****n
发帖数: 1093 | 35 回头研究一下二爷的DP
leetcode的OJ搞得真不错，收获很大，希望多加些有代表性的新题做做，谢谢 |
|
p*****2
发帖数: 21240 | 36
看LZ的情况，只会recursion貌似会跪。所以准备一下DP，说不定还能把面试官搞糊涂
了。 |
|
i**********e
发帖数: 1145 | 37 那为什么 TLE 呢？
难道是java不稳定？
我转成c++试一试。 |
|
p*****2
发帖数: 21240 | 38
时间是n*m, 空间是n
时间复杂度高所以会TLE |
|
|
h****n
发帖数: 1093 | 40 试过了二爷的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+... 阅读全帖 |
|
|
b***m
发帖数: 5987 | 42 俺不会DP。二爷在西雅图地区吗？我请你吃饭，给我讲讲DP呗。 |
|
b***m
发帖数: 5987 | 43 M家呀，今天是个Senior Test Lead，做File Server的。 |
|
i**********e
发帖数: 1145 | 44 你可以看看我这个是不是跟你一样的啊？
为什么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... 阅读全帖 |
|
h****n
发帖数: 1093 | 45 额，一旦出现TLE我这里没法显示之前通过或者没通过的那些cases。。试了几个浏览器
都不行 |
|
|
|
i**********e
发帖数: 1145 | 48 你现在再试一试好吗？
我暂时把那个最大的large case去除掉了。 |
|
i**********e
发帖数: 1145 | 49 run 了啊。
java 除了那个最大的case之外，全都过了。
但是我转成C++就错了两三个。hychin转换你的程序也过了，所以我在想我的程序是否
有问题。能帮我看看吗？ |
|
p*****2
发帖数: 21240 | 50
DP一顿饭估计也讲不清楚，不过这题的应该能讲明白。你住哪里？ |
|
