Published Oct 27, 2021
[
Given an input string s and a pattern p, implement regular expression matching with support for . and * where:
. Matches any single character.* Matches zero or more of the preceding element.The matching should cover the entire input string (not partial).
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
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".
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".
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".
Input: s = "mississippi", p = "mis*is*p*."
Output: false
1 <= s.length <= 201 <= p.length <= 30s contains only lowercase English letters.p contains only lowercase English letters, ., and *.*, there will be a previous valid character to match.If there were no *, we can simply check from left to right if each character
of the text matches the pattern.
def match(text, pattern):
if not pattern: return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
return first_match and match(text[1:], pattern[1:])
If a * is present in the pattern, it will be in the second position
pattern[1]. Then, we may ignore this part of the pattern, or delete a matching
character. If we have a match on the remaining strings after any of these
operations, then the initial inputs matched.
class Solution(object):
def isMatch(self, text, pattern):
if not pattern:
return not text
first_match = bool(text) and pattern[0] in {text[0], '.'}
if len(pattern) >= 2 and pattern[1] == '*':
return (self.isMatch(text, pattern[2:]) or
first_match and self.isMatch(text[1:], pattern))
else:
return first_match and self.isMatch(text[1:], pattern[1:])
As the problem has optimal substructure, it is natural to cache intermediate
results. Because calls will only ever be made to match(test[i:], pattern[j:]),
we use dp(i, j) to handle those calls instead, saving us expensive
string-building operations and allowing us to cache the intermediate results
class Solution(object):
def isMatch(self, text, pattern):
memo = {}
def dp(i, j):
if (i, j) not in memo:
if j == len(pattern):
ans = i == len(text)
else:
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j+1 < len(pattern) and pattern[j+1] == '*':
ans = dp(i, j+2) or first_match and dp(i+1, j)
else:
ans = first_match and dp(i+1, j+1)
memo[i, j] = ans
return memo[i, j]
return dp(0, 0)
function isMatch(s: string, p: string): boolean {
// the memo object should be a global one
const memo = {};
// i, j are indexes for s & p
const dp = (i, j) => {
// make unique string key here
const key = i + ',' + j
// if key is not in memo, update it
if(!(key in memo)) {
let res;
// final result
// if we are at the pattern end, i should also be at string end for it to match
if (j === p.length) {
res = i === s.length
} else {
// check valid i & string match on pattern
const firstMatch = i < s.length && [s[i], '.'].includes(p[j])
// if we have '*', either ignore previous, or count once
if(j + 1 < p.length && p[j + 1] === '*') {
res = dp(i, j + 2) || (firstMatch && dp(i + 1, j))
} else {
// if we dont have the '*' check firstMatch & remaining
res = firstMatch && dp(i + 1, j + 1);
}
}
memo[key] = res;
}
// return the value with key
return memo[key];
};
// let's start at the beginning
return dp(0, 0);
}
class Solution(object):
def isMatch(self, text, pattern):
dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]
dp[-1][-1] = True
for i in range(len(text), -1, -1):
for j in range(len(pattern) - 1, -1, -1):
first_match = i < len(text) and pattern[j] in {text[i], '.'}
if j+1 < len(pattern) and pattern[j+1] == '*':
dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
else:
dp[i][j] = first_match and dp[i+1][j+1]
return dp[0][0]