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

写一下我的思路吧，希望帮助大家理解。

首先状态转移矩阵表示每个pattern的字符对每个str字符的匹配结果，这个结果不仅需要考虑当前字符的匹配结果，还要考虑之前的字符匹配结果。

1、边界条件

当pattern长度为0时，只有str长度为0可以认为匹配成功，所以dp[0][0]=true; str长度不为0的话，都是匹配失败，所以dp[i][0]都是false；

当str长度为0时，pattern长度为0，同上一条；pattern长度不为0的话，只有出现'*'，并且'*'前面只有一个字符，这时这个字符可以出现0次，这里可以认为是匹配成功，所以再看'*'向前数第二个字符的匹配状态（只要前面都是"字符*字符*。。"这样的，就可以匹配成功），并转移下来，即dp[0][j]=dp[0][j-2]，因此这里可以放到后面状态转移中一起计算。

2、状态转移

dp[i][j]对应的pattern字符和str字符分别为pattern[i-1]和str[j-1],他们的关系有如下情况：

1、pattern[i-1]等于str[j-1]，或者pattern[i-1]是'.'，这两种情况都可以匹配成功，因此转移前一个pattern和前一个str字符的匹配状态就好，所以dp[i][j]=dp[i-1][j-1]。（因为只有这一位匹配成功没用，需要所有都成功，才是真的成功）

2、pattern[i-1]不等于str[j-1]，但是pattern[i-1]是'*'，这种情况下其实有两种匹配方式：一是'*'使它之前的字符匹配变为0；一是'*'匹配当前字符。

当'*'使它之前的字符匹配变为0时，状态回退到dp[i][j-2]（回退*和*之前的字符，总共两个，所以j-2）如果对于第j-2个pattern可以匹配当前第i个字符的话，那么，这个*也认为可以匹配了，反之亦然，所以：dp[i][j]=dp[i][j-2]

当'*'匹配当前字符时，就要求前导字符为'.'或者等于当前字符。也就是pattern[i-2]等于str[j-1]，或者pattern[i-2]是'.'。这个时候我们就可以开始转移前一个状态，也就是上一个字符的匹配状态，上一个字符的匹配状态也分为两种，一是上一个字符也是由这个*匹配的，即d[i-1][j]=true，二是上一个字符是由这个*的前第二个字符匹配d[i-1][j-2]=true（意思是假设*前面是a，即a*，如果前一个字符是由*匹配，也就是由a*可以匹配；如果前一个字符不与*匹配，那么a*也无法匹配，即前一个字符不是a，只能由a*之前的字符匹配，即d[i-1][j-2]）所以我们的状态转移关系应该是：dp[i][j]=d[i-1][j]||d[i-1][j-2]。但是这个式子是可以简化的。因为我们知道*是可以使状态回退到前面第二个字符的，即，如果d[i-1][j-2]是true，d[i-1][j]也肯定是true，所以得到dp[i][j]=d[i-1][j]。（这里存在d[i-1][j-2]是false，d[i-1][j]也是true的情况，即d[i-1][j]也是由这个*匹配但是与前面的pattern都不匹配，这种就是*匹配一连串相同字符的情况，所以每个字符的匹配状态都是由前一个字符匹配*转移来的）。

还有一点要注意的是即使*的前导字符与当前字符相同，仍然可以选择匹配0个，例如用"aa*"去匹配"a"虽然a*可以匹配a，此时不存在前一个str字符，所以仍然要匹配0个。因此此时的状态转移方程要包含匹配0个的的情况，即dp[i][j]=d[i-1][j]||d[i][j-2]

综上，当pattern为*时，仅当*前导字符等于当前要匹配的字符或'.'时，多出一种前置状态d[i-1][j]，其余情况都可以选择由匹配0个的状态d[i][j-2]来转移，加上一些边界条件判断，代码如下所示

if(pattern.charAt(j-1)=='*'){
       if(i>0&&j>1&&(pattern.charAt(j-2)=='.'||pattern.charAt(j-2)==str.charAt(i-1)))
	   		dp[i][j]=dp[i-1][j]||dp[i][j-2];
       else 
	   		dp[i][j]=dp[i][j-2];
                }

3、pattern不是*，.，也不等于str[j-1]，那就很简单的不匹配，也不需要状态转移了，dp[i][j]=false;

所以完整的java代码如下：

public static boolean match (String str, String pattern) {
        int l1=str.length(),l2=pattern.length();
        boolean[][] dp=new boolean[l1+1][l2+1];
        dp[0][0]=true;

        for(int i=0;i<l1+1;i++){
            for(int j=1;j<l2+1;j++){
                if(i>0&&(str.charAt(i-1)==pattern.charAt(j-1)||pattern.charAt(j-1)=='.'))dp[i][j]=dp[i-1][j-1];
                else if(pattern.charAt(j-1)=='*'){
                    if(i>0&&j>1&&(pattern.charAt(j-2)=='.'||pattern.charAt(j-2)==str.charAt(i-1)))dp[i][j]=(dp[i-1][j]||dp[i-1][j-2])||dp[i][j-2];
                    else dp[i][j]=dp[i][j-2];
                }
            }
        }
        return dp[l1][l2];
    }