題目

描述

給你一個字符串 s 和一個字符規(guī)律 p，請你來實現(xiàn)一個支持 '.' 和 '*' 的正則表達式匹配。

'.' 匹配任意單個字符
'*' 匹配零個或多個前面的那一個元素

所謂匹配，是要涵蓋整個字符串s的，而不是部分字符串。
說明:

• s 可能為空，且只包含從 a-z 的小寫字母。
• p 可能為空，且只包含從 a-z 的小寫字母，以及字符 . 和 *。

示例 1:

輸入:
s = "aa"
p = "a"
輸出: false
解釋: "a" 無法匹配 "aa" 整個字符串。

示例 2:

輸入:
s = "aa"
p = "a*"
輸出: true
解釋: 因為 '*' 代表可以匹配零個或多個前面的那一個元素, 在這里前面的元素就是 'a'。因此，字符串 "aa" 可被視為 'a' 重復(fù)了一次。

示例 3:

輸入:
s = "ab"
p = ".*"
輸出: true
解釋: ".*" 表示可匹配零個或多個（'*'）任意字符（'.'）。

示例 4:

輸入:
s = "aab"
p = "c*a*b"
輸出: true
解釋: 因為 '*' 表示零個或多個，這里 'c' 為 0 個, 'a' 被重復(fù)一次。因此可以匹配字符串 "aab"。

示例 5:

輸入:
s = "mississippi"
p = "mis*is*p*."
輸出: false

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/regular-expression-matching
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。

解答

思路

使用動態(tài)規(guī)劃的方法：

1. 狀態(tài)矩陣：dp[i][j] 表示s的前i個字符是否可以被p的前j個字符匹配.
2. 轉(zhuǎn)移方程：
   2.1 如果p[j] == s[j]，那么dp[i][j] = dp[i-1][j-1]
   2.2 如果p[j] == '.'，那么dp[i][j] = dp[i-1][j-1]
   2.3 如果p[j] == '*'：
   2.3.1 如果p[j - 1] != s[i]，那么dp[i][j] = dp[i][j-2] // 也就是說*匹配了個寂寞，讓前面的字符無效了
   2.3.2 如果p[j - 1] == s[i]或者p[j-1] == '.'：
   - 要么dp[i][j] = dp[i-1][j] // * 匹配到了多個字符
   - 要么dp[i][j] = dp[i][j-1] // * 匹配了一個字符
   - 要么dp[i][j] = dp[i][j-2] // * 匹配了個寂寞

代碼

class Solution {
    public boolean isMatch(String s, String p) {
        if (s == null || p == null) {
            return false;
        }
        int m = s.length(), n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;
        // ""和匹配關(guān)系的初始化
        // 奇數(shù)位不管什么字符都是false，偶數(shù)位為*時，dp[0][i] = dp[0][i-2]
        for (int i = 2; i <= n; i += 2) {
            if (p.charAt(i - 1) == '*') {
                dp[0][i] = dp[0][i - 2];
            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char sc = s.charAt(i - 1);
                char pc = p.charAt(j - 1);
                if (sc == pc || pc == '.') {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (pc == '*') {
                    if (dp[i][j - 2]) {
                        dp[i][j] = true;
                    } else if (sc == p.charAt(j - 2) || p.charAt(j - 2) == '.') {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }
        return dp[m][n];
    }
}