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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @param pattern string字符串 
     * @return bool布尔型
     */
    public boolean match (String s, String p) {
        // write code here
        s = " " + s;
        p = " " + p;

        boolean[][] dp = new boolean[s.length()][p.length()];
        // 长度都为0时，认为匹配
        dp[0][0] = true;
        // str的长度为0，pattern长度不为0，有可能可以匹配上。
        // pattern的长度为0，str长度不为0，有可能可以匹配上。
        // 所以 dp[i][0]一定为false，不需要讨论
        for (int i = 0; i < s.length(); i++) {
            for (int j = 1; j < p.length(); j++) {

                // pattern中下一个字符为*时不参与匹配
                if (j < p.length() - 1 && p.charAt(j + 1) == '*'){
                    continue;
                }

                // 讨论当前字符是否为 *
                // 是 *
                if (p.charAt(j) != '*'){
                    dp[i][j] = (i >= 1 && j>= 1 && dp[i - 1][j - 1]) //前面的字符串匹配
                              && (p.charAt(j) == '.' || s.charAt(i) == p.charAt(j)); //当前字符匹配
                }
                // 非 *
                if (p.charAt(j) == '*'){
                    dp[i][j] = (j >= 2 && dp[i][j - 2]) // 匹配0个字符

                             || i >= 1 &&  (dp[i - 1][j] &&     // 匹配多个字符
                                    (p.charAt(j - 1) == s.charAt(i)  //pattern前一个字符和当前字符相等
                                    || p.charAt(j - 1) == '.'));            //pattern前一个字符为'.'
                }
            }
        }
        return dp[s.length() - 1][p.length() - 1];
    }
}