r*****a
发帖数: 421 | 1 用recursive brutal force的算法leetcode通过了small data test，
但是在large data test的时候超时了。
尤其是以下这个例子，自己电脑上都算不出来。
s="bbbababbbbabbbbababbaaabbaababbbaabbbaaaabbbaaaabb"
p="*b********bb*b*bbbbb*ba"
有没有更优化的算法？
贴个java的
public boolean wildcardMatch(String s, String p, int sPos, int pPos) {
if (sPos == s.length()) {
if (pPos == p.length()) // p also used up
return true;
} else if (pPos < p.length() && p.charAt(pPos) == '*') { // current p
is *, rest should all be *
return wildcardMatch(s, p, sPos, pPos + 1);
} else {
return false;
}
} else {
if (pPos == p.length()) { // s hasn't used up but p used up
return false;
} else if (pPos < p.length() && sPos < s.length() // find match both
move 1
&& (p.charAt(pPos) == '?' || p.charAt(pPos) == s.charAt(sPos))
) {
return wildcardMatch(s, p, sPos + 1, pPos + 1);
} else if (pPos < p.length() && p.charAt(pPos) == '*') { // is *,
match one or zero.
return wildcardMatch(s, p, sPos + 1, pPos) || wildcardMatch(s, p,
sPos, pPos + 1);
} else {
return false;
}
}
} |
p*****2
发帖数: 21240 | |
C***U
发帖数: 2406 | 3 有iterative 的算法 可以通过judge large
【在 p*****2 的大作中提到】
: 这题小数据过了就差不多了。
|
p*****2
发帖数: 21240 | 4
感觉面试的话recursion或者DP就够了吧？
【在 C***U 的大作中提到】
: 有iterative 的算法 可以通过judge large
|
C***U
发帖数: 2406 | 5 Recursion超时
iterative不会 但是那个iterative写起来挺难
看这里
http://blog.sina.com.cn/s/blog_60b5450101016nmp.html
【在 p*****2 的大作中提到】
:
: 感觉面试的话recursion或者DP就够了吧？
|
p*****2
发帖数: 21240 | 6
我的意思是面试的标准不会以leetcode big data能不能pass为标准吧？
【在 C***U 的大作中提到】
: Recursion超时
: iterative不会 但是那个iterative写起来挺难
: 看这里
: http://blog.sina.com.cn/s/blog_60b5450101016nmp.html
|
C***U
发帖数: 2406 | 7 恩 这个对哦 看面试官心情 和你和他的缘分
哈哈哈
【在 p*****2 的大作中提到】
:
: 我的意思是面试的标准不会以leetcode big data能不能pass为标准吧？
|
p*****2
发帖数: 21240 | 8
其实面试recursion能写到bug free已经挺牛逼的了。好多题我知道最优的面试也不敢
用。自己handle不了更麻烦。
【在 C***U 的大作中提到】
: 恩 这个对哦 看面试官心情 和你和他的缘分
: 哈哈哈
|
C***U
发帖数: 2406 | 9 恩
谢谢指教
增加了一点信心 因为我现在很难写到bug free
一般都要调试才能改对
【在 p*****2 的大作中提到】
:
: 其实面试recursion能写到bug free已经挺牛逼的了。好多题我知道最优的面试也不敢
: 用。自己handle不了更麻烦。
|
p*****2
发帖数: 21240 | 10
现在能做到一遍写对的只有wwwyhx吧。
【在 C***U 的大作中提到】
: 恩
: 谢谢指教
: 增加了一点信心 因为我现在很难写到bug free
: 一般都要调试才能改对
|
w*******2
发帖数: 8 | |
