| 40 | // } |
| 41 | |
| 42 | public boolean isMatch(String s, String p) { |
| 43 | if (p.length() == 0) return s.length() == 0; |
| 44 | int sL = s.length(), pL = p.length(); |
| 45 | boolean[][] dp = new boolean[sL + 1][pL + 1]; |
| 46 | char[] sc = s.toCharArray(), pc = p.toCharArray(); |
| 47 | dp[0][0] = true; |
| 48 | for (int i = 2; i <= pL; ++i) { |
| 49 | if (pc[i - 1] == '*' && dp[0][i - 2]) { |
| 50 | dp[0][i] = true; |
| 51 | } |
| 52 | } |
| 53 | for (int i = 1; i <= sL; ++i) { |
| 54 | for (int j = 1; j <= pL; ++j) { |
| 55 | if (pc[j - 1] == '.' || pc[j - 1] == sc[i - 1]) { |
| 56 | dp[i][j] = dp[i - 1][j - 1]; |
| 57 | } |
| 58 | if (pc[j - 1] == '*') { |
| 59 | if (pc[j - 2] == sc[i - 1] || pc[j - 2] == '.') { |
| 60 | dp[i][j] = dp[i - 1][j] || dp[i][j - 2]; |
| 61 | } else { |
| 62 | dp[i][j] = dp[i][j - 2]; |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | } |
| 67 | return dp[sL][pL]; |
| 68 | } |
| 69 | |
| 70 | public static void main(String[] args) { |
| 71 | Solution solution = new Solution(); |