abab bas ab* b.*
(s string, p string)
| 12 | // ab* b.* |
| 13 | |
| 14 | func isMatch(s string, p string) bool { |
| 15 | m := make(map[[2]int]bool) |
| 16 | var dp func(i, j int) bool |
| 17 | dp = func(i, j int) bool { |
| 18 | if _, ok := m[[2]int{i, j}]; !ok { |
| 19 | var ans bool |
| 20 | if j == len(p) { |
| 21 | ans = i == len(s) |
| 22 | } else { |
| 23 | firstMatch := i < len(s) && (p[j] == s[i] || p[j] == '.') |
| 24 | if j+1 < len(p) && p[j+1] == '*' { |
| 25 | ans = dp(i, j+2) || firstMatch && dp(i+1, j) |
| 26 | } else { |
| 27 | ans = firstMatch && dp(i+1, j+1) |
| 28 | } |
| 29 | } |
| 30 | m[[2]int{i, j}] = ans |
| 31 | } |
| 32 | return m[[2]int{i, j}] |
| 33 | } |
| 34 | return dp(0, 0) |
| 35 | } |