剑指offer19.正则表达式

 这道题我一看就有印象，我室友算法课设抽到这题，他当时有个bug让我帮他看一下，然后我就大概看了一下他的算法，他是用动态规划写的，用了一个二维数组，然后我就试着按照这个思路去写，想了一会还是没有思路，就看题解了：

class Solution {public boolean isMatch(String s, String p) {// .可以代替所有字符，*前面的一个字符可以出现任意次包括0次int m = s.length();int n = p.length();boolean[][] dp = new boolean[m+1][n+1];dp[0][0] = true;for(int i =0; i<=m; i++){for(int j=1;j<=n;j++){if(p.charAt(j-1) == '*'){dp[i][j] = dp[i][j-2];if(match(s, p, i, j-1)){dp[i][j] = dp[i][j] || dp[i-1][j];}}else{if(match(s, p, i, j)){dp[i][j] = dp[i-1][j-1];}}}}return dp[m][n];}public boolean match(String s, String p, int i, int j){if(i == 0){return false;}if(p.charAt(j-1) == '.'){return true;}return s.charAt(i-1) == p.charAt(j-1);}}

dp[i][i]表示s的前i个字符与p的前j个是否匹配，进行状态转移时考虑p的第j个字符：

1，如果第j个字符是一个字母，那么必须在s中匹配一个相同的小写字母。

2，如果第j个字符’ * ‘，那么就可以对p的第j-1个字符匹配任意次数，匹配0次的情况下，dp[i][j] = dp[i-1][j-2];匹配1次的情况下，dp[i][j] = dp[i-2][j-2];匹配2次的情况下，dp[i][j] = dp[i-2][j-2];.......

 所以综合两种情况有：

 matches（）是判断两个字符是否匹配的方法，如果字符相同或者模板中的字符是' . '就返回true否则返回false。

dp[0][0] = true,当两个字符是空字符时返回true，最后返回dp[m][n],m是s的长度，n是p的长度。