登录
  • #刷题
  • #leetcode

Wildcard Matching这题我用backtracking来写怎么就速度那么慢?

刹那刹哪
624
1
额外写了个backtrack函数来写 而不是答案的那种two point的方法 感觉原理应该是一样的 但是我这个运行时间只超过了5%的人 还得再用cache来剪枝

是因为recursive stack的缘故么?但是这个不是应该只跟space有关么

[mw_shl_code=java,true]class Solution {

HashSet<String> failed;

public boolean isMatch(String s, String p) {

failed = new HashSet<>();

return backtrack(s, p, 0, 0);

}

private boolean backtrack(String s, String p, int si, int pi) {

if (pi == p.length() && si == s.length()) return true;

if (failed.contains(si + " " + pi)) {

// System.out.println(si + " " + pi);

return false;

}

boolean res = false;

if (pi == p.length() || (si == s.length() && p.charAt(pi) != '*')) res = false;

else if (p.charAt(pi) == '*') {

if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') res = backtrack(s, p, si, pi + 1);

else {

for (int i = si; i <= s.length(); i++) {

if (backtrack(s, p, i, pi + 1)) {

res = true;

break;

}

}

}

} else {

if (p.charAt(pi) != '?' && s.charAt(si) != p.charAt(pi)) res = false;

else res = backtrack(s, p, si + 1, pi + 1);

}

if (!res) failed.add(si + " " + pi);

return res;

}

}[/mw_shl_code]
1条回复
热度排序

发表回复