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

额外写了个backtrack函数来写 而不是答案的那种two point的方法 感觉原理应该是一样的 但是我这个运行时间只超过了5%的人 还得再用cache来剪枝
是因为recursive stack的缘故么？但是这个不是应该只跟space有关么

1. class Solution {
   
2.    HashSet<String> failed;
   
3. 
   
4.     public boolean isMatch(String s, String p) {
   
5.         failed = new HashSet<>();
   
6.         return backtrack(s, p, 0, 0);
   
7.     }
   
8. 
   
9.     private boolean backtrack(String s, String p, int si, int pi) {
   
10.         if (pi == p.length() && si == s.length()) return true;
    
11.         if (failed.contains(si + " " + pi)) {
    
12.             // System.out.println(si + " " + pi);
    
13.             return false;
    
14.         }
    
15.         boolean res = false;
    
16.         if (pi == p.length() || (si == s.length() && p.charAt(pi) != '*')) res = false;
    
17.         else if (p.charAt(pi) == '*') {
    
18.             if (pi + 1 < p.length() && p.charAt(pi + 1) == '*') res = backtrack(s, p, si, pi + 1);
    
19.             else {
    
20.                 for (int i = si; i <= s.length(); i++) {
    
21.                     if (backtrack(s, p, i, pi + 1)) {
    
22.                         res = true;
    
23.                         break;
    
24.                     }
    
25.                 }
    
26.             }  
    
27.         } else {
    
28.             if (p.charAt(pi) != '?' && s.charAt(si) != p.charAt(pi)) res = false;
    
29.             else res = backtrack(s, p, si + 1, pi + 1);
    
30.         }
    
31.         if (!res) failed.add(si + " " + pi);
    
32.         return res;
    
33.     }
    
34. }

复制代码

额下面不用回复了。。。看答案直接跳过了方法一 其实就是我这种 Recursion with memorisation
速度慢的原因是The first idea here is a recursion. That's a straightforward approach but quite time consuming because of huge recursion depth for long input strings.