正则表达式匹配

题目描述

请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配

 1 public class Solution {
 2     public boolean match(char[] str, char[] pattern)
 3     {
 4         int m = str.length, n = pattern.length;
 5         boolean [][] dp = new boolean[n + 1][m + 1];
 6         dp[0][0] = true;
 7         for (int i = 1; i <= n; ++i) {
 8             for (int j = 0; j <= m; ++j) {
 9                 if (pattern[i - 1] == '*') {
10                     if (dp[i - 2][j]) dp[i][j] = true;
11                     if (j > 0 && 
12                         (pattern[i - 2] == '.' || str[j - 1] == pattern[i - 2])
13                         && (dp[i - 2][j - 1] || dp[i][j - 1]))
14                         dp[i][j] = true;
15                 } else {
16                     if (j != 0) {
17                         if ((pattern[i - 1] == '.' || pattern[i - 1] == str[j - 1])
18                            && dp[i - 1][j - 1])
19                             dp[i][j] = true;
20                     }
21                 }
22             }
23         }
24         return dp[n][m];
25     }
26 }