題⽬描述

請實現⼀個函數⽤來匹配包括' . '和' * '的正則表達式。模式中的字符' . '表示任意⼀個字符，
⽽' * '表示它前⾯的字符可以出現任意次（包含0 次）。 在本題中，匹配是指字符串的所有字符匹配整個模式。例如，字符串" aaa "與模式" a.a "和" ab*ac*a "匹配，但是與" aa.a "和" ab*a "均不匹
配

示例1
輸⼊: "aaa","a*a"
返回值: true

示例2
輸⼊："aad","c*a*d"
返回值：true
説明：因為這⾥ c 為 0 個，a被重複⼀次， * 表示零個或多個a。因此可以匹配字符串 "aad"。

示例3
輸⼊："",".*"
返回值：true
説明：".*" 表示可匹配零個或多個（'*'）任意字符（'.'）

思路及解答

遞歸

分類討論，原串定義為str ,模式串為pattern 。`

• 如果pattern ⻓度為0

  • 且str ⻓度為0 ,説明剛剛好匹配完，返回ture
  • str ⻓度不為0 ，説明沒有匹配完，返回false

• 如果pattern 的⻓度⼤於0

  • 如果pattern 的⻓度⼤於1 ，且第2 個字符是* ，説明前⾯的字符可以匹配0 ， 1 或者多次

    • 分為兩種情況討論：⼀種是直接把 和 前⾯的字符去掉，相當於匹配了0 個，然後接着⽐較；另外⼀種是，如果str 的⻓度⼤於0 ，並且第⼀個字符匹配，那就把str 的第⼀個字符去掉，兩者接着匹配。
  • 否則，説明第⼆個字符不是 * ，那麼就直接⽐較第⼀個字符是不是匹配，同時將後⾯的字符進⾏匹配。

注意：上⾯説的第⼀個字符是不是匹配，除了兩個字符相等的情況，其實還有模式串的字符為' . '的情況。

public class Solution {
    public boolean isMatch(String s, String p) {
        // 模式串為空時，文本串也必須為空才匹配
        if (p.isEmpty()) return s.isEmpty();
        
        // 檢查首字符匹配：文本串非空且字符相等或模式為'.'
        boolean firstMatch = !s.isEmpty() && 
                            (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
        
        // 處理'*'通配符（確保模式長度≥2且第二個字符是'*'）
        if (p.length() >= 2 && p.charAt(1) == '*') {
            // 兩種情況：1) '*'匹配0個前驅字符 2) 匹配1個及以上前驅字符
            return isMatch(s, p.substring(2)) || 
                   (firstMatch && isMatch(s.substring(1), p));
        } else {
            // 無'*'情況：首字符匹配且剩餘部分也匹配
            return firstMatch && isMatch(s.substring(1), p.substring(1));
        }
    }
}

• 時間複雜度：最壞O((m+n)2^(m+n))

• 空間複雜度：O(m²+n²)遞歸棧

  記憶化搜索（遞歸+緩存）

在遞歸基礎上添加緩存，避免重複計算。使用二維數組存儲s[i:]和p[j:]的匹配結果，避免重複遞歸

public class Solution {
    private Boolean[][] memo; // 緩存數組：null未計算，true/false已計算
    
    public boolean isMatch(String s, String p) {
        memo = new Boolean[s.length() + 1][p.length() + 1];
        return dfs(0, 0, s, p);
    }
    
    private boolean dfs(int i, int j, String s, String p) {
        // 檢查緩存是否存在當前子問題的解
        if (memo[i][j] != null) return memo[i][j];
        
        boolean result;
        // 模式串耗盡時，文本串也必須耗盡
        if (j == p.length()) {
            result = (i == s.length());
        } else {
            // 計算當前首字符匹配狀態
            boolean firstMatch = (i < s.length()) && 
                                (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.');
            
            // 處理'*'通配符
            if (j + 1 < p.length() && p.charAt(j + 1) == '*') {
                result = dfs(i, j + 2, s, p) || // 匹配0次
                        (firstMatch && dfs(i + 1, j, s, p)); // 匹配1+次
            } else {
                result = firstMatch && dfs(i + 1, j + 1, s, p);
            }
        }
        memo[i][j] = result; // 存儲結果到緩存
        return result;
    }
}

• 時間複雜度：O(m×n)

• 空間複雜度：O(m×n)

  動態規劃（推薦）

動態規劃：

1. ⾸先定義狀態：⽤⼀個⼆維數組（套路） dp[i][j] ⽤來表示str 的前i 個字符和pattern 的前j 個字符是否匹配。

2. 初始化簡單狀態

   • 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. 如果dp[i][j-2]==true ，那麼dp[i][j]=true (相當於str的前i和pattern的前j-2個字符匹配，此時的* 前⾯的那個字符出現了0 次)。
      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 次）
      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]！='*' )

      1. 如果dp[i - 1][j - 1]=true and str[i - 1] == pattern[j - 1] 時，則dp[i][j]=true 。（也就是前⾯匹配，接下來的字符⼀樣匹配）
      2. 如果dp[i - 1][j - 1]=true 且pattern[i-1]=='.' ，那麼dp[i][j]=true 。(其實也是. 可以匹配任何字符)

處理完數組之後，最後返回dp[n-1][m-1] ，也就是str 的前n 個和pattern 的前m 個字符是否匹配。

public boolean match(String str, String pattern) {
    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];
}

• 時間複雜度 O(mn) ： 其中 m , n 分別為 str 和 pattern 的⻓度，狀態轉移需遍歷整個 dp 矩陣。
• 空間複雜度 O(mn) ： 狀態矩陣 dp 使⽤ O(mn) 的額外空間。

狀態機優化（空間優化DP）

狀態機優化：滾動數組降低空間複雜度，只保留當前行和上一行的狀態，空間優化到O(n)

public class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[] dp = new boolean[n + 1];
        boolean[] prev = new boolean[n + 1];
        
        // 初始化第一行（空文本串情況）
        dp[0] = true;
        for (int j = 2; j <= n; j++) {
            if (p.charAt(j - 1) == '*') {
                dp[j] = dp[j - 2];
            }
        }
        
        for (int i = 1; i <= m; i++) {
            // 保存上一行狀態
            boolean[] temp = prev;
            prev = dp;
            dp = temp;
            
            // 初始化當前行首列
            dp[0] = false;
            for (int j = 1; j <= n; j++) {
                char sc = s.charAt(i - 1);
                char pc = p.charAt(j - 1);
                
                if (pc == '*') {
                    char prevChar = p.charAt(j - 2);
                    boolean matchZero = dp[j - 2];
                    boolean matchMulti = (prevChar == sc || prevChar == '.') && prev[j];
                    dp[j] = matchZero || matchMulti;
                } else {
                    dp[j] = (pc == '.' || pc == sc) && prev[j - 1];
                }
            }
        }
        
        return dp[n];
    }
}

• 時間複雜度：O(m×n)
• 空間複雜度：O(n)