LeetCode 0010 - Regular Expression Matching
# Hints
- DP
# 题面
Difficulty | Time Complexity Limit | Extra-Memory Complexity Limit |
---|---|---|
Medium |
Given an input string s
and a pattern p
, implement regular expression matching with support for '.'
and '*'
.
'.'
Matches any single character.
'*'
Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s
could be empty and contains only lowercase letters a-z
.
p
could be empty and contains only lowercase letters a-z
, and characters like .
or *
.
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 (.)".
Example 4:
Input:
s = "aab"
p = "c*a*b"
Output: true
Explanation: c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
Input:
s = "mississippi"
p = "mis*is*p*."
Output: false
# 题意
给定一个输入串 和一个规则串 ,要求对 整个 执行以 为规则的正则表达式匹配,要求支持以下规则:
.
可以匹配任意一个字符。x*
可以匹配零或多个字符 。
输入保证 仅包含小写字母, 仅包含小写字母和字符 .
和 *
。
# 题解
考虑动态规划,设 表示 和 是否可以匹配,则 即为答案。
状态转移方程:
$\begin{cases} dp[0][0] = 1, &(initialize) \ dp[0][j] = dp[0][j-2],\ &(j \in [2,\ m],\ p[j-1] == '') \ dp[i][j] = dp[i-1][j-1], &(i \in [1,\ n],\ j \in [1,\ m],\ match(i-1,\ j-1)) \ dp[i][j] = dp[i][j-2] \mid dp[i-1][j], &(i \in [1,\ n],\ j \in [2,\ m],\ p[j-1] == '',\ match(i-1,\ j-2)) \ dp[i][j] = dp[i][j-2], &(i \in [1,\ n],\ j \in [2,\ m],\ p[j-1] == '*',\ !match(i-1,\ j-2)) \end{cases}$
其中 表示 和 可以匹配。这个状态转移有点复杂,但其实并不难,我们逐条解释。
第一条很显然,第二条先不去管它;
第三条很简单,当 或 时,我们直接匹配一个字符即可,即 由 转移。
第四条和第五条用于处理 x*
匹配。当 x*
匹配零次时, 可以由 转移,当 x*
匹配一或多次时, 可以由 转移。
回过来看,第二条其实就是 x*
匹配的边界条件。
时间复杂度为 ,其中 表示 的长度。
也可以考虑DFS,本题的特征确实很容易先想到搜索,我们可以在实现完成后再转化为记忆化搜索。虽然思路不同,但是所得结果的本质是相同的。
实际上,本题写成DFS其实会有些复杂,下面也提供了一种代码实现。如果先预处理掉边界情况的话,代码实现还会比这简单不少。
# AC代码
class Solution {
public:
bool isMatch(string s, string p) {
// 初始化
int n = s.length(), m = p.length();
bool dp[n + 5][m + 5];
memset(dp, false, sizeof(dp));
dp[0][0] = true;
// 递推
for (int j = 2; j <= m; j ++) {
if (p[j - 1] == '*') {
dp[0][j] = dp[0][j - 2];
}
}
for (int i = 1; i <= n; i ++) {
for (int j = 1; j <= m; j ++) {
// 通常匹配
if (match(s[i - 1], p[j - 1])) {
dp[i][j] |= dp[i - 1][j - 1];
}
// x*匹配
else if (j >= 2 && p[j - 1] == '*') {
// 匹配零次
dp[i][j] |= dp[i][j - 2];
// 匹配更多一次
if (match(s[i - 1], p[j - 2])) {
dp[i][j] |= dp[i - 1][j];
}
}
}
}
// 返回
return dp[n][m];
}
// 判断是否匹配
inline bool match(char si, char pj) {
return (si == pj || pj == '.');
}
};
# AC代码
class Solution {
public:
bool isMatch(string s, string p) {
// 初始化
int n = s.length(), m = p.length();
int ** dp = new int * [n + 5];
for (int i = 0; i < n + 5; i ++) {
dp[i] = new int[m + 5];
memset(dp[i], -1, (m + 5) * sizeof(int));
}
// DFS
bool res = dfs(s, p, 0, 0, dp);
// 释放
for (int i = 0; i < n + 5; i ++) {
delete[] dp[i];
}
delete[] dp;
// 返回
return res;
}
// 深度优先搜索
bool dfs(const string & s, const string & p, int i, int j, int ** dp) {
// 记忆化搜索
if (dp[i][j] != -1) {
return dp[i][j];
}
// 递归终止:规则串为空的情况
else if (j == p.length()) {
dp[i][j] = (i == s.length());
}
// 递归:x*匹配零次的情况
else if (j + 1 < p.length() && p[j + 1] == '*' && dfs(s, p, i, j + 2, dp)) {
dp[i][j] = true;
}
// 递归终止:输入串为空的情况
else if (i == s.length()) {
dp[i][j] = false;
}
// 递归终止:匹配失败的情况
else if (s[i] != p[j] && p[j] != '.') {
dp[i][j] = false;
}
// 递归:x*匹配多次的情况
else if (j + 1 < p.length() && p[j + 1] == '*') {
dp[i][j] = dfs(s, p, i + 1, j, dp);
}
// 递归
else {
dp[i][j] = dfs(s, p, i + 1, j + 1, dp);
}
// 返回
return dp[i][j];
}
};
- 01
- Reading Papers - Kernel Concurrency06-01
- 02
- Linux Kernel - Source Code Overview05-01
- 03
- Linux Kernel - Per-CPU Storage05-01