A*H
发帖数: 127 | 1 是一定code有问题么，还是有可能程序跑得不够快?
wildcard matching 那题，small test 过了，large test 一直timeout, 大家帮忙看
看这个java code有什么问题么? 除了暴力法，还有更快得解法么？
public boolean isMatch(String s, String p) {
return match(s, p, 0, 0);
}
public boolean match(String s1, String s2, int i1, int i2) {
int l1 = s1.length();
int l2 = s2.length();
if (i2 == l2) return i1 == l1;
if (s2.charAt(i2) == '*') {
while (i2
i2++; // find next non * character
while (i1 < l1) {
if (match(s1, s2, i1++, i2))
return true;
}
return match(s1, s2, i1, i2); //when i1 ends
} else if (i1 < l1 &&
(s2.charAt(i2) == '?' || s1.charAt(i1) == s2.charAt(i2))) {
return match(s1, s2, i1+1, i2+1);
}
return false;
} | h****e
发帖数: 928 | 2 暴力是不行的，一定要有一些优化。你可以就return false看
LeetCode的测试数据是什么，然后一个个试过去。你肯定会
找到至少对于一个测试数据你的程序要运行>>1分钟的。打印出
一些调试信息你就可以知道为什么哪里运行慢了。 | B*******1
发帖数: 2454 | 3 在function里面加多一个参数， count，每次recursive ＋ 1, 计算现在在哪里一层内
循环， 如果超过一定数目，直接return false，一样就可以看出hang在哪个case了。 | b**********g
发帖数: 90 | 4 不用递归，用DP做，不会timeout。
【在 A*H 的大作中提到】
: 是一定code有问题么，还是有可能程序跑得不够快?
: wildcard matching 那题，small test 过了，large test 一直timeout, 大家帮忙看
: 看这个java code有什么问题么? 除了暴力法，还有更快得解法么？
: public boolean isMatch(String s, String p) {
: return match(s, p, 0, 0);
: }
: public boolean match(String s1, String s2, int i1, int i2) {
: int l1 = s1.length();
: int l2 = s2.length();
: if (i2 == l2) return i1 == l1;
| b**********g
发帖数: 90 | 5 不用递归，用DP做，不会timeout。
【在 A*H 的大作中提到】
: 是一定code有问题么，还是有可能程序跑得不够快?
: wildcard matching 那题，small test 过了，large test 一直timeout, 大家帮忙看
: 看这个java code有什么问题么? 除了暴力法，还有更快得解法么？
: public boolean isMatch(String s, String p) {
: return match(s, p, 0, 0);
: }
: public boolean match(String s1, String s2, int i1, int i2) {
: int l1 = s1.length();
: int l2 = s2.length();
: if (i2 == l2) return i1 == l1;
| p*****2
发帖数: 21240 | 6 我写了一个DP的怎么还是超时呢？
哪里可以改善？
public boolean isMatch(String s, String p)
{
int m = s.length();
int n = p.length();
boolean[][] dp = new boolean[2][n + 1];
dp[0][0] = true;
for (int j = 1; j <= n; j++)
{
if (p.charAt(j - 1) == '*')
dp[0][j] = dp[0][j - 1];
}
for (int i = 1; i <= m; i++)
{
int curr=i%2;
int prev=(i+1)%2;
Arrays.fill(dp[curr],false);
for (int j = 1; j <= n; j++)
{
if (s.charAt(i - 1) == p.charAt(j - 1)
|| p.charAt(j - 1) == '?')
dp[curr][j] = dp[prev][j - 1];
if (p.charAt(j - 1) == '*')
dp[curr][j] = dp[prev][j]||dp[curr][j-1];
}
}
return dp[m%2][n];
} |
|
