class Solution {
public boolean isMatch(String s, String p) {
return s.matches(p);
}
}
Runtime: 38 ms, faster than 28.71% of Java online submissions for Regular Expression Matching.
Memory Usage: 39.7 MB, less than 8.76% of Java online submissions for Regular Expression Matching.
:)
class Solution {
public boolean isMatch(String text, String pattern) {
if (pattern.isEmpty()) return text.isEmpty();
boolean first_match = (!text.isEmpty() &&
(pattern.charAt(0) == text.charAt(0) || pattern.charAt(0) == '.'));
if (pattern.length() >= 2 && pattern.charAt(1) == '*'){
return (isMatch(text, pattern.substring(2)) ||
(first_match && isMatch(text.substring(1), pattern)));
} else {
return first_match && isMatch(text.substring(1), pattern.substring(1));
}
}
}
Runtime: 137 ms, faster than 5.46% of Java online submissions for Regular Expression Matching.
Memory Usage: 114.3 MB, less than 5.03% of Java online submissions for Regular Expression Matching.
Recursion
class Solution {
public boolean isMatch(String text, String pattern) {
boolean[][] dp = new boolean[text.length() + 1][pattern.length() + 1];
dp[text.length()][pattern.length()] = true;
for (int i = text.length(); i >= 0; i--){
for (int j = pattern.length() - 1; j >= 0; j--){
boolean first_match = (i < text.length() &&
(pattern.charAt(j) == text.charAt(i) ||
pattern.charAt(j) == '.'));
if (j + 1 < pattern.length() && pattern.charAt(j+1) == '*'){
dp[i][j] = dp[i][j+2] || first_match && dp[i+1][j];
} else {
dp[i][j] = first_match && dp[i+1][j+1];
}
}
}
return dp[0][0];
}
}
Runtime: 2 ms, faster than 90.30% of Java online submissions for Regular Expression Matching.
Memory Usage: 37.6 MB, less than 93.66% of Java online submissions for Regular Expression Matching.
dp bottom-up