题解 | #正则表达式匹配#

思路采用采用动态规划。当p[i]==''时,需要判断两种情况，dp[ i-1][j]的情况和s[i]==p[j-1]||p[j-1]=='.'时，dp[i][j-2]的情况。当p[i]==''时，dp[i][j-2]为真时，说明当前这个p[j]和p[j-1]不用参与匹配（就是'*'匹配了前面一个字符0次的情况）。当s[i]==p[j-1]||p[j-1]=='.'时，若dp[i-1][j]为真，则说明当前这个‘ * '已经参与了前面的字符匹配,必然可以继续通配,此时只需要再复制一个字符即可达到匹配。由于 ‘ * ’ 一次只能匹配前面字符0个或者1个，因此所有情况都被包揽了，最后只需要找到dp数组最右下角的值即可。

public class Solution {
    public boolean match (String str, String pattern) {
        str="-"+str;
        pattern = "-"+pattern;
        boolean dp[][] = new boolean[str.length()][pattern.length()];
        dp[0][0] = true;
        char[] s = str.toCharArray();
        char[] p = pattern.toCharArray();
        for(int i = 0;i<s.length;++i){
            for(int j=1;j<p.length;++j){
                if(s[i]==p[j]||p[j]=='.'){
                    if(i-1>=0)dp[i][j] = dp[i-1][j-1];
                }
                else if(p[j]=='*'){
                    if(j>=2&&dp[i][j-2]) dp[i][j] = true;
                    else if(s[i]==p[j-1]||p[j-1]=='.')
                        if(i-1>=0)
                            dp[i][j] = dp[i-1][j];
                }
            }
        }
        return dp[s.length-1][p.length-1];
    }
}