| 7 | } |
| 8 | |
| 9 | private boolean dfs(boolean[][] cache, String s, String p, int i, int j) { |
| 10 | if (cache[i][j] != false) return cache[i][j]; |
| 11 | |
| 12 | if (i >= s.length() && j >= p.length()) return true; |
| 13 | |
| 14 | if (j >= p.length()) return false; |
| 15 | |
| 16 | boolean match = |
| 17 | i < s.length() && |
| 18 | (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.'); |
| 19 | |
| 20 | if (j + 1 < p.length() && p.charAt(j + 1) == '*') { |
| 21 | cache[i][j] = |
| 22 | dfs(cache, s, p, i, j + 2) || |
| 23 | (match && dfs(cache, s, p, i + 1, j)); |
| 24 | } else { |
| 25 | cache[i][j] = match && dfs(cache, s, p, i + 1, j + 1); |
| 26 | } |
| 27 | |
| 28 | return cache[i][j]; |
| 29 | } |
| 30 | } |