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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String str, String pattern) {
        // write code here
                if (pattern.length() == 0) {
            return str.length() == 0;
        }
        int n = str.length() + 1;
        int m = pattern.length() + 1;
        boolean[][] dp = new boolean[n][m];
        dp[0][0] = true;
        for (int j = 2; j < m; j = j + 2) {
            if (dp[0][j - 2] && pattern.charAt(j - 1) == '*') {
                dp[0][j] = true;
            }
        }
        for (int i = 1; i < n; i++) {
            for (int j = 1; j < m; j++) {
                if (pattern.charAt(j - 1) == '*') {
                    dp[i][j] = dp[i][j - 2]
                            || dp[i - 1][j] && (str.charAt(i - 1)
                            == pattern.charAt(j - 2)
                            || pattern.charAt(j - 2) == '.');
                } else {
                    dp[i][j] = dp[i - 1][j - 1] && (str.charAt(i -
                            1) == pattern.charAt(j - 1)
                            || pattern.charAt(j - 1) == '.');
                }
            }
        }
        return dp[n - 1][m - 1];
    }
}

解题思想：动态规划

* 1. ⾸先我们需要 定义状态 ：⽤⼀个⼆维数组（套路） dp[i][j] ⽤来表示 str 的前 i 个字符和 pattern 的前 j 个字符是否匹配。

* 2. 接下来，我们需要 初始化简单状态 ，因为想要求后⾯的状态，是依赖于前⾯的状态的，⼀般是初始化 dp[i][j] 的⾸⾏和⾸列。

* dp[0][0]= true ,表示两个空的字符串是匹配的。

* dp 数组的⾸列，除了 dp[0][0] 为 true ，其他的都是 false 。因为pattern为空，但是s不为空的时候，肯定不匹配。

* dp 的⾸⾏，也就是str为空的时候，如果pattern的偶数位都是“*”,那么就可以匹配，因为可以选择匹配0次。

* 3. 初始化前⾯之后，后⾯的从索引 1 开始匹配：

* 1. pattern 的第 j 个字符为“ * ”(即是 pattern[j-1]=='*' )

* 1.1 如果 dp[i][j-2]==true ，那么 dp[i][j]=true (相当于str的前i和pattern的前j-2个字符匹配，此时的 * 前⾯的那个字符出现了 0 次)。

* 1.2 如果 dp[i-1][j]==true 且 str[i-1]==pattern[j-2] ，则 dp[i][j] =true 。（如果 str 的前 i - 1 个字符和 pattern 的前 j 个字符匹配，并且 str 的第 i 个字符和 pattern 的第 j - 1 个字符相等,相当于‘ * ’前⾯的字符出现了 1 次）

* 1.3 如果 dp[i-1][j]=true 且 pattern[j-2]=='.' 的时候，则 dp[i][j]=true 。(表示 str 的前 i-1 个和 patten 的前 j 个匹配，并且 pattern 的第 j-1 个是‘ . ’，第 j 个是‘ * ’,那么说明可以匹配任何字符任何次数，⾃然 str 可以多匹配⼀个字符。)

* 2. pattern 的第 j 个字符不为“ * ”(即是 pattern[j-1]！='*' )

* 2.1 如果 dp[i - 1][j - 1]=true and str[i - 1] == pattern[j- 1] 时，则 dp[i][j]=true 。（也就是前⾯匹配，接下来的字符⼀样匹配）

* 2.2 如果 dp[i - 1][j - 1]=true 且 pattern[i-1]=='.' ，那么 dp[i][j]=true 。(其实也是 . 可以匹配任何字符)

* 处理完数组之后，最后返回 dp[n-1][m-1] ，也就是 str 的前 n 个和 pattern 的前 m个字符是否匹配。