Skip to content

發布日期: March 28, 2024

最後更新: March 28, 2024

閱讀時間: ~ 3 min


LeetCode 44. Wailcard Matching

題目

44. Wailcard Matching

解題思路

這種需要用兩個字串做計算的題目通常預設就是開一個二維陣列,然後決定垂直與水平軸分別表示哪個字串。這題我將假設二維陣列為 dp,垂直軸表示 s 字串,水平軸表示 p 字串。

狀態定義

狀態很簡單,dp[i][j] 表示 s0 ~ i 個字元與 p0 ~ j 個字元是否匹配。

狀態轉移函式

在 dp[i][j] 狀態時,p[j] 可能出現的字元種類分為三種情況 (這裡就不列出狀態轉移的數學式了,直接看三種情況分析)。

1. p[j] == '?'

此時 dp[i][j] = dp[i - 1][j - 1],因為 '?' 能匹配任意字元,因此狀態等於 dp[i - 1][j - 1]

2. p[j] == '*'

此時 dp[i][j] = dp[i][j - 1] || dp[i - 1][j],因為 '*' 可以匹配任意長度字元或空字元,而 dp[i][j - 1] 表示 '*' 為空字串,dp[i - 1][j] 表示 '*' 匹配 s[i] 的字元,因此只要任一個狀態為 truedp[i][j] 就是 true

3. p[j] 為英文字母

此時 dp[i][j] 則取決於 s[i]p[j] 是否相等,若相等則 dp[i][j] 等於 dp[i - 1][j - 1],若不相等表示不匹配。

程式碼

cpp
class Solution {
public:
  bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();

    // 初始化 dp 陣列,注意這裡要多一行多一列,因為 s 與 p 有可能是空字串,index 0 表示空字串。
    // 由於多了一行一列,所以後續 dp[i][j] 對應到的是 s[i - 1] 和 p[j - 1]。
    vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
    // 初始狀態
    dp[0][0] = true;
    // p 為空字串時,s 只要不是空字串就一定不匹配
    for (int i = 1; i <= m; ++i) {
      dp[i][0] = false;
    }
    // s 為空字串時,p 如果是 '*' 就需要看前一個狀態是否為 true 才能匹配
    // p 如果是 '?' 或英文字母,則一定不匹配,因為 s 是空字串
    for (int j = 1; j <= n; ++j) {
      dp[0][j] = p[j - 1] == '*' ? dp[0][j - 1] : false;
    }

    for (int i = 1; i <= m; ++i) {
      for (int j = 1; j <= n; ++j) {
        // 實作上述狀態轉移分析的三種情況
        if (p[j - 1] == '?') {
          dp[i][j] = dp[i - 1][j - 1];
        } else if (p[j - 1] == '*') {
          dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
        } else {
          dp[i][j] = s[i - 1] == p[j - 1] ? dp[i - 1][j - 1] : false;
        }
      }
    }

    return dp[m][n];
  }
};