10. Regular Expression Matching
給定一個輸入字串 s 和一個模式 p，實作支援 '.' 和 '*' 的正則表達式匹配，其中：'.' 匹配任何單個字元。
'*' 匹配零個或多個前面的元素。 匹配應涵蓋整個輸入字串（不允許部分匹配）。
Python
class Solution:
def isMatch(self, s: str, p: str) -> bool:
# Initialize the memoization table
memo = {}
def dp(i, j):
# Check if the result is already computed
if (i, j) in memo:
return memo[(i, j)]
# Base case: if the pattern is exhausted, check if the string is also
exhausted
if j == len(p):
return i == len(s)
# Check if the current characters match
first_match = i < len(s) and (p[j] == s[i] or p[j] == '.')
# Handle the '*' wildcard
if j + 1 < len(p) and p[j + 1] == '*':
memo[(i, j)] = (dp(i, j + 2) or
(first_match and dp(i + 1, j)))
else:
memo[(i, j)] = first_match and dp(i + 1, j + 1)
return memo[(i, j)]
return dp(0, 0)
16.70MB, 48ms
C++
#include <string>
#include <vector>
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length();
int n = p.length();
// Create a DP table with dimensions (m+1) x (n+1)
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1, false));
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Fill the first row for patterns like a*, a*b*, a*b*c*
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// Fill the DP table
for (int i = 1; i <= m; ++i) {
for (int j = 1; j <= n; ++j) {
if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2]; // Treat * as zero occurrence
if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
// Treat * as one or more occurrences
}
}
}
}
return dp[m][n];
}
};
9.12MB, 4ms
Javascript
/**
* @param {string} s
* @param {string} p
* @return {boolean}
*/
var isMatch = function(s, p) {
// Create a DP table with dimensions (m+1) x (n+1)
const m = s.length;
const n = p.length;
const dp = Array.from(Array(m + 1), () => Array(n + 1).fill(false));
// Base case: empty pattern matches empty string
dp[0][0] = true;
// Fill the first row for patterns like a*, a*b*, a*b*c*
for (let j = 1; j <= n; ++j) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}
// Fill the DP table
for (let i = 1; i <= m; ++i) {
for (let j = 1; j <= n; ++j) {
if (p[j - 1] == '.' || p[j - 1] == s[i - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else if (p[j - 1] == '*') {
dp[i][j] = dp[i][j - 2]; // Treat * as zero occurrence
if (p[j - 2] == '.' || p[j - 2] == s[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j];
// Treat * as one or more occurrences
}
}
}
}
return dp[m][n];
};
51.74MB, 73ms
