三刷 07/2022
Version #2 DP
Time O(MN)
Space O(MN)
Runtime: 4 ms, faster than 70.69% of Java online submissions for Regular Expression Matching.
Memory Usage: 42.5 MB, less than 72.14% of Java online submissions for Regular Expression Matching.
class Solution {
public boolean isMatch(String s, String p) {
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
for (int i = 0; i <= s.length(); i++) {
for (int j = 0; j <= p.length(); j++) {
if (j == 0) {
dp[i][j] = i == 0;
continue;
}
char pc = p.charAt(j - 1);
if (pc == '*') {
dp[i][j] = dp[i][j - 2]; // match zero
if (i > 0 && (p.charAt(j - 2) == '.' || p.charAt(j - 2) == s.charAt(i - 1))) {
// s - ba
// p - a*
dp[i][j] |= dp[i - 1][j];
}
continue;
}
if (i > 0 && (pc == s.charAt(i - 1) || pc == '.')) {
dp[i][j] = dp[i - 1][j - 1];
}
}
}
return dp[s.length()][p.length()];
}
}
Version #1 DFS without Memorization
Runtime: 33 ms, faster than 37.09% of Java online submissions for Regular Expression Matching.
Memory Usage: 42.7 MB, less than 59.04% of Java online submissions for Regular Expression Matching.
class Solution {
public boolean isMatch(String s, String p) {
return match(s, 0, p, 0);
}
private boolean match(String s, int sIndex, String p, int pIndex) {
if (sIndex == s.length() && pIndex == p.length()) {
return true;
}
if (pIndex >= p.length()) {
return false;
}
char c = p.charAt(pIndex);
if (pIndex + 1 < p.length() && p.charAt(pIndex + 1) == '*') {
if (match(s, sIndex, p, pIndex + 2)) {
return true;
}
while (sIndex < s.length() && (c == '.' || s.charAt(sIndex) == c)) {
if (match(s, sIndex + 1, p, pIndex + 2)) {
return true;
}
sIndex++;
}
return false;
}
return sIndex < s.length() && (s.charAt(sIndex) == c || c == '.') && match(s, sIndex + 1, p, pIndex + 1);
}
}
二刷
89.63 %
class Solution {
public boolean isMatch(String s, String p) {
// s
// c c c
// T F F F
// c F T F F
// * T T T T
// a F
// * T
// b F
// if match char or . dp[i][j] = dp[i - 1][j - 1]
// if * check if match (j - 1) -> dp[i][j] = dp[j - 2][i - 1] || dp[j - 1][i] || dp[j][i - 1]
boolean[][] dp = new boolean[p.length() + 1][s.length() + 1];
dp[0][0] = true;
for (int j = 1; j <= p.length(); j++) {
if (p.charAt(j - 1) == '*') {
dp[j][0] = dp[j - 2][0];
} else {
dp[j][0] = false;
}
}
for (int i = 1; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
char cs = s.charAt(i - 1);
char cp = p.charAt(j - 1);
if (cp == '*') {
dp[j][i] = dp[j - 2][i] || dp[j - 1][i];
if (p.charAt(j - 2) == cs || p.charAt(j - 2) == '.') {
dp[j][i] = dp[j][i] || dp[j][i - 1];
}
} else {
if (cs == cp || cp == '.') {
dp[j][i] = dp[j - 1][i - 1];
} else {
dp[j][i] = false;
}
}
}
}
return dp[p.length()][s.length()];
}
}
一刷
Bug:
"aaa", "ab*a*c*a"
如果遇到 j == * -> a*
可以match a
-> 0 个 -> dp[i][j - 2]
-> 1 个 -> dp[i][j - 1]
-> 2 个 -> given previous matched 1 or more -> dp[i - 1][j] (this a* has matched before?)
62.23 %
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) {
return false;
}
boolean[][] dp = new boolean[s.length() + 1][p.length() + 1];
dp[0][0] = true; // All the other dp[i][0] should be false
for (int i = 0; i <= s.length(); i++) {
for (int j = 1; j <= p.length(); j++) {
if (i == 0) {
if (p.charAt(j - 1) == '*') {
dp[i][j] = dp[i][j - 2];
} else {
dp[i][j] = false;
}
} else {
if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.') {
dp[i][j] = dp[i - 1][j - 1];
} else if (p.charAt(j - 1) == '*') {
if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
// match 0
dp[i][j] = dp[i][j - 2] || dp[i][j - 1] || dp[i - 1][j];
} else {
dp[i][j] = dp[i][j - 2];
}
}
}
}
}
return dp[s.length()][p.length()];
}
}
Version #1 Simple DFS without memorization
二刷
主要是很多edge case
譬如 a -> ab*
aa -> a*
aa -> .*
24.50 %
class Solution {
public boolean isMatch(String s, String p) {
if (s == null || p == null) return false;
// 1. if character -> check equal
// 2. if . -> continue
// 3. if character + * -> dfs to match 0 ~ several characters
return helper(s, 0, p, 0);
}
private boolean helper(String s, int sIndex, String p, int pIndex) {
if (pIndex == p.length()) return sIndex == s.length();
if (pIndex == p.length() - 1 || pIndex + 1 < p.length() && p.charAt(pIndex + 1) != '*') {
if (sIndex < s.length() && (p.charAt(pIndex) == '.' || p.charAt(pIndex) == s.charAt(sIndex))) {
return helper(s, sIndex + 1, p, pIndex + 1);
}
} else {
int currIndex = sIndex - 1;
while (currIndex < sIndex || (currIndex < s.length() && (s.charAt(currIndex) == p.charAt(pIndex) || p.charAt(pIndex) == '.'))) {
if (helper(s, currIndex + 1, p, pIndex + 2)) return true;
currIndex++;
}
}
return false;
}
}
一刷
19.30 %
对*match 0 to several characters的情况进行枚举搜索，如果遇到true则可以返回true
s和p不一定同时搜索到最后，有可能s到尾但p还有一些c*，也有可能是true
所以以p到结尾为标准，p到结尾以后如果s也被match完则true
如果p后面不存在c*但s到了结尾，则一定是false了
public class Solution {
public boolean isMatch(String s, String p) {
return isMatch(s, p, 0, 0);
}
public boolean isMatch(String s, String p, int stringIndex, int patternIndex) {
if (patternIndex == p.length()) return stringIndex == s.length();
if (patternIndex == p.length() - 1 || (patternIndex < p.length() - 1 && p.charAt(patternIndex + 1) != '*')) {
if (stringIndex >= s.length()) return false;
if (p.charAt(patternIndex) == '.' || p.charAt(patternIndex) == s.charAt(stringIndex)) {
return isMatch(s, p, stringIndex + 1, patternIndex + 1);
} else return false;
}
if (patternIndex < p.length() - 1 && p.charAt(patternIndex + 1) == '*') {
//match 0 characters in string
if (isMatch(s, p, stringIndex, patternIndex + 2)) return true;
//match 1 to more characters
while (stringIndex < s.length()) {
if (p.charAt(patternIndex) != '.' && s.charAt(stringIndex) != p.charAt(patternIndex)) return false;
if (isMatch(s, p, stringIndex + 1, patternIndex + 2)) return true;
stringIndex++;
}
}
return false;
}
}
No comments:
Post a Comment