LeetCode 10 Regular Expression Matching
概述
https://leetcode.com/problems/regular-expression-matching/
动态规划法
状态：dp[i][j] 是一个布尔数组，表示 string[i:] 和 pattern[j:] 能否匹配成功。
选择：对于 pattern 中的字母和 . 并没有选择可言；对于 *，我们可以选择匹配其之前的字母 0~N 次，放到递归中则是匹配或者不匹配。
- 匹配：则 pattern 保持不变，string 进一位。
- 不匹配，则 string 保持不变，pattern 进两位（因为 * 和其之前的字符为一个整体）。
注意：
- 为了代码的可读性，使用一个专门的布尔数组来记录 memory 中是否有之前计算过的值。
- 注意需要妥善处理边界情况。
代码：
class Solution {
String s, p;
boolean[][] data;
boolean[][] computed;
public boolean isMatch(String s, String p) {
this.s = s;
this.p = p;
data = new boolean[s.length()+1][p.length()+2];
computed = new boolean[s.length()+1][p.length()+2];
return dp(0, 0);
}
private boolean dp(int i, int j) {
// When pattern is over, return true if the string also is over.
if(j>=p.length()) return i>=s.length();
boolean current = false;
if(i<s.length()) {
if(computed[i][j]) return data[i][j];
current = (s.charAt(i) == p.charAt(j)) || (p.charAt(j) == '.');
}
// Notice the * pattern must act with its previous character.
if(p.length() > j+1 && p.charAt(j+1) == '*') data[i][j] = dp(i, j+2) || (current && dp(i+1, j));
else data[i][j] = current && dp(i+1, j+1);
computed[i][j] = true;
return data[i][j];
}
}
2022年2月19日的动态规划解法
佛了，读错题目了，* 不是匹配任意值，而是匹配其之前的值的任意次。
错误理解下的解法：
class Solution {
public:
vector<vector<int>> dp;
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
dp.resize(s.size(), vector<int>(p.size(), -1));
return helper(0, 0);
}
bool helper(int i, int j) {
if (i == s.size() && j == p.size()) return true;
if (i == s.size() || j == p.size()) return false;
if (dp[i][j] != -1) return dp[i][j];
if (p[j] == '.' || p[j] == s[i]) {
dp[i][j] = helper(i+1, j+1);
} else if (p[j] == '*') {
int nexti = i;
while (nexti < s.size()) {
dp[i][j] = helper(nexti++, j+1);
if (dp[i][j]) break;
}
} else {
dp[i][j] = false;
}
return dp[i][j];
}
};
我们应当将 a* 等理解为一个特殊字符（即作为一个整体处理），这样的话，我们应该在处理当前值的时候，看一下后续值是否为 * 。
class Solution {
public:
vector<vector<int>> dp;
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
dp.resize(s.size(), vector<int>(p.size(), -1));
return helper(0, 0);
}
bool helper(int i, int j) {
if (i == s.size() && j == p.size()) return true;
if (j == p.size()) return false;
if (i == s.size()) {
// the rest must be c* pairs if it want to be true
if (p.size() - j % 2 == 1) return false;
for (; j + 1 < p.size(); j += 2) {
if (p[j+1] != '*') return false;
}
return true;
}
if (dp[i][j] != -1) return dp[i][j];
if (j + 1 < p.size() && p[j+1] == '*') {
if (dp[i][j]) return true;
if (p[j] == '.' || p[j] == s[i]) {
int nexti = i;
while (p[j] == '.' || p[j] == s[nexti]) {
if (nexti > s.size()) break;
dp[i][j] = helper(nexti++, j+2);
if (dp[i][j]) break;
}
} else {
dp[i][j] = helper(i, j+2);
}
} else {
if (p[j] == '.' || p[j] == s[i]) {
dp[i][j] = helper(i+1, j+1);
} else {
dp[i][j] = false;
}
}
return dp[i][j];
}
};
之前想复杂了，搞了个循环出来：
int nexti = i;
while (p[j] == '.' || p[j] == s[nexti]) {
if (nexti > s.size()) break;
dp[i][j] = helper(nexti++, j+2);
if (dp[i][j]) break;
}
实际上没有必要，可以用迭代的形式避免这种显式的循环：
class Solution {
public:
vector<vector<int>> dp;
string s;
string p;
bool isMatch(string s, string p) {
this->s = s;
this->p = p;
dp.resize(s.size(), vector<int>(p.size(), -1));
return helper(0, 0);
}
bool helper(int i, int j) {
if (j == p.size()) return i == s.size();
if (i == s.size()) {
// the rest must be c* pairs if it want to be true
if ((p.size() - j) % 2 == 1) return false;
for (; j + 1 < p.size(); j += 2) {
if (p[j+1] != '*') return false;
}
return true;
}
if (dp[i][j] != -1) return dp[i][j];
if (j + 1 < p.size() && p[j+1] == '*') {
if (p[j] == '.' || p[j] == s[i]) {
dp[i][j] = helper(i, j+2) || helper(i+1, j);
} else {
dp[i][j] = helper(i, j+2);
}
} else {
if (p[j] == '.' || p[j] == s[i]) {
dp[i][j] = helper(i+1, j+1);
} else {
dp[i][j] = false;
}
}
return dp[i][j];
}
};