10. Regular Expression Matching

  • Hardness: \(\color{red}\textsf{Hard}\)
  • Ralated Topics: String、Dynamic Programming、Recursion

一、題目

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

  • '.' Matches any single character.
  • '*' Matches zero or more of the preceding element.
    The matching should cover the entire input string (not partial).

Example 1:

  • Input: s = “aa”, p = “a”
  • Output: false
  • Explanation: “a” does not match the entire string “aa”.

Example 2:

  • Input: s = “aa”, p = “a*”
  • Output: true
  • Explanation: ‘*’ means zero or more of the preceding element, ‘a’. Therefore, by repeating ‘a’ once, it becomes “aa”.

Example 3:

  • Input: s = “ab”, p = “.*”
  • Output: true
  • Explanation: “.*” means “zero or more (*) of any character (.)”.

Constraints:

  • 1 <= s.length <= 20
  • 1 <= p.length <= 30
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '.', and '*'.
  • It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

二、分析

  • 觀察規律：
    • 當 p 為空時，若 s 不為空回傳 false， s 為空回傳 true。
    • 當 p 不為空時，分為以下情況：
      • 當 *p 為英文字元，則 *s 必定為相同的英文字元，否則回傳 false。
      • 當 *p 為 . 時，則 *s 可以為任意英文字元。
      • 當 *p 為 * 時，則 *s 可以為 ' '、前一相符的字合，在此稱為 firstMatch。

三、解題

1. DFS

  • Time complexity: \(O(C(m+n,m))，\text{m }為\text{ s }的長度，\text{n }為\text{ p }的長度\)，
    \(\begin{array}{l} T(m,n)=T(m,n-2)+T(m-1,n-2)+T(m-2,n-2)+…+T(1,n-2)\\ T(m-1,n)=T(m-1,n-2)+T(m-2,n-2)+…+T(1,n-2)\\ T(m,n)=T(m-1,n)+T(m,n-2)\\ T(0,n)=n, T(m,0)=1\\ \end{array}\)

  • Space complexity: \(O(C(m+n,m))\)

int m, n;
string s, p;
bool isMatch(string s, string p) {
    this->s = s;
    this->p = p;
    this->m = s.length();
    this->n = p.length();
    
    return dfs(0, 0);
}
// 分別對應到 s 的第 i 個字元與 p 的第 j 個字元
bool dfs(int i, int j) {
    // 當 p 為空時，若 s 不為空回傳 false，s 為空回傳 true。
    if (j == n) return i == m;
    // firstMatch 的情形
    bool firstMatch = i < m && (s[i] == p[j] || p[j] == '.');
    // *p 為 '*' 的情形
    if (j+1 < n && p[j+1] == '*')
        return dfs(i, j+2) || (firstMatch && dfs(i+1, j));
    return firstMatch && dfs(i+1, j+1);    
}

2. DFS + DP(Top Bottom)

  • Time complexity: \(O(m\times n)，\text{m }為\text{ s }的長度，\text{n }為\text{ p }的長度\)，
  • Space complexity: \(O(m\times n)\)
int m, n;
string s, p;
vector<vector<int>> dp;
bool isMatch(string s, string p) {
    this->m = s.length();
    this->n = p.length();
    this->s = s;
    this->p = p;
    dp = vector<vector<int>>(m+1, vector<int>(n+1, -1));    // 用 dp[i][j] 記錄 s 前進 i 位與 p 前進 j 位的狀況

    return dfs(0, 0);
}
bool dfs(int i, int j) {
    if (dp[i][j] != -1) return dp[i][j];
    if (j == n) {
        dp[i][j] = i == m;
        return dp[i][j];
    }
    bool firstMatch = i < m && (s[i] == p[j] || p[j] == '.');
    if (j+1 < n && p[j+1] == '*')
        dp[i][j] = dfs(i, j+2) || (firstMatch && dfs(i+1, j));
    else 
        dp[i][j] = firstMatch && dfs(i+1, j+1);
    return dp[i][j];
}

3. DP (Bottom Up)

  • Time complexity: \(O(m\times n)，\text{m }為\text{ s }的長度，\text{n }為\text{ p }的長度\)，
  • Space complexity: \(O(m\times n)\)
bool isMatch(string s, string p) {
    int m = s.length(), n = p.length();
    if (n == 0) return m == 0;
    
    bool dp[m+1][n+1];
    memset(dp, false, sizeof(dp));
    dp[0][0] = true;

    for (int i = 2; i <= n; i++) {
        if (p[i-1] == '*') {
            dp[0][i] = dp[0][i-2];
        }
    }

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (s[i-1] == p[j-1] || p[j-1] == '.') {
                dp[i][j] = dp[i-1][j-1];
            } else if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2] || ((s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j]);
            }
        }
    }
    return dp[m][n];
}

回目錄 Catalog