# 10. Regular Expression Matching
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 precedeng 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
# Solution
Approach 1: recursion.
Approach 2: DP.
# Code (Python)
Approach 1:
def isMatch(self, string: str, pattern: str) -> bool:
# recursion (TLE)
if not pattern:
return not string
if not string:
if not pattern:
return True
if len(pattern) >= 2 and pattern[1] == '*': # len(pattern) matters
return self.isMatch(string, pattern[2:])
else:
return False
if len(pattern) < 2 or pattern[1] != '*':
if not string or (pattern[0] != '.' and string[0] != pattern[0]):
return False
return self.isMatch(string[1:], pattern[1:])
else:
# consider pattern 'x*xxx' as a whole because we need the previous char
return self.isMatch(string, pattern[2:]) or self.isMatch(string, pattern[0] + pattern[0] + pattern[2:]) or (self.isMatch(string[1:], pattern) and (string[0] == pattern[0] or pattern[0] == '.'))
Approach 2:
def isMatch(self, string: str, pattern: str) -> bool:
# table[i][j] -- string[:i] matches pattern[:j]
table = [[False for _ in range(len(pattern) + 1)] for _ in range(len(string) + 1)]
table[0][0] = True
for j in range(2, len(pattern) + 1):
if pattern[j-1] == '*':
table[0][j] = table[0][j-2] # e.g. 'a*b*c*d*' matches ''
for i in range(1, len(string) + 1):
for j in range(1, len(pattern) + 1):
if pattern[j-1] == '.':
table[i][j] = table[i-1][j-1]
elif pattern[j-1] == '*': # a pattern can't start with a *, which guarantees j >= 2
table[i][j] = table[i][j-1] or table[i][j-2] or (table[i-1][j] and (string[i-1] == pattern[j-2] or pattern[j-2] == '.')) # repeat the previous char 1 time, 0 time, and 2+ times
else:
table[i][j] = table[i-1][j-1] and string[i-1] == pattern[j-1]
return table[-1][-1]
# Code (C++)
Approach 1:
class Solution {
private:
unordered_map<string,bool> umap;
public:
bool isMatch(string s, string p) {
if (p.size() == 0)
return s.size() == 0;
string key = s + "," + p;
if (umap.find(key) != umap.end())
return umap[key];
bool match = false;
if (p.size() > 1 && p[1] == '*')
{
match = isMatch(s, p.substr(2)) ||
(s.size() > 0 && (p[0] == '.' || p[0] == s[0]) && isMatch(s.substr(1), p));
}
else
{
match = s.size() > 0 && (p[0] == '.' || p[0] == s[0]) &&
isMatch(s.substr(1), p.substr(1));
}
umap[key] = match;
return match;
}
};
Approach 2:
class Solution {
public:
bool isMatch(string s, string p) {
int sSize = s.size();
int pSize = p.size();
bool match[sSize+1][pSize+1];
match[sSize][pSize] = true;
for (int i = 0; i < sSize; ++i)
match[i][pSize] = false;
for (int i = sSize; i >= 0; --i)
{
for (int j = pSize-1; j >= 0; --j)
{
if (j < pSize-1 && p[j+1] == '*')
continue;
if (p[j] == '*')
{
match[i][j] = match[i][j+1] ||
(i < sSize && (p[j-1] == '.' || p[j-1] == s[i]) && match[i+1][j]);
match[i][j-1] = match[i][j];
}
else
{
match[i][j] = i < sSize && (p[j] == '.' || p[j] == s[i]) &&
match[i+1][j+1];
}
}
}
return match[0][0];
}
};