LC 0010 [H] Regular Expression Matching - ALawliet/algorithms GitHub Wiki
i think the recursive solution is a little easier to understand, tricky part is base case and to get the indexes and edge cases right
think in edge cases:
match = s[i] == p[j] or p[j] == '.'
if there is a *:
don't use it (iterate pattern +2) => dfs(i, j+2)
or use it (iterate str +1) => match and dfs(i+1, j)
else if there is a match:
(iterate both +1) => dfs(i+1, j+1)
else no match:
return False
(check for a match)
T[i-1][j-1] if str[i] == pattern[j] or pattern[j] == '.' # take diag
---
(check for a *, use it or don't use it)
T[i][j-2] if pattern[j] == '*' # try without this char so take 2 back
OR T[i-1][j] if str[i] == pattern[j-1] or pattern[j-1] == '.' # if that fails then check 1 pattern back and take 1 str up if they match
---
(no match and no *)
False
x a *
x
a
x
x
a
x a *
x
class Solution(object):
def isMatch(self, s, p):
@lru_cache()
def dfs(i, j):
if i >= len(s) and j >= len(p):
return True
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
if (j + 1) < len(p) and p[j + 1] == '*':
# don't use * or use *
return dfs(i, j + 2) or (match and dfs(i + 1, j))
if match:
return dfs(i + 1, j + 1)
return False
return dfs(0, 0)
class Solution(object):
def isMatch(self, s, p):
# i points str, j points pattern
cache = {}
def dfs(i, j):
if (i, j) in cache:
return cache[(i, j)]
# reached end at same time
if i >= len(s) and j >= len(p):
return True
# ran out of the pattern before finishing str
if j >= len(p):
return False
match = i < len(s) and (s[i] == p[j] or p[j] == '.')
# check * first, it takes precedence
if (j + 1) < len(p) and p[j + 1] == '*':
# don't use * or use *
# double jump horizontal or jump vertical
cache[(i,j)] = dfs(i, j + 2) or (match and dfs(i + 1, j))
return cache[(i,j)]
if match:
# jump diagonal
cache[(i,j)] = dfs(i + 1, j + 1)
return cache[(i,j)]
cache[(i,j)] = False
return False
return dfs(0, 0)
class Solution(object):
def match(self, s, i, p, j):
if i == len(s) or j == len(p):
return False
return p[j] == '.' or s[i] == p[j]
def helper(self, s, i, p, j):
# Base Cases
if j == len(p):
return i == len(s)
# to cover the case of "abc" ".*"
if i > len(s):
return False
# 1. if second is * p[i+1]
if j < len(p)-1 and p[j+1] == '*':
# Zero means advance p[j+2]
# one or more compare and advance if match
return (self.match(s, i, p, j) and self.helper(s, i+1, p, j)) or self.helper(s, i, p, j+2)
# 2. Match either same or '.'
if self.match(s, i, p, j):
return self.helper(s, i+1, p, j+1)
# 3. No match or *
return False
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
return self.helper(s, 0, p, 0)
cheese
class Solution(object):
@lru_cache()
def isMatch(self, s, p):
if not p:
return not s
if p[-1] == '*':
if self.isMatch(s, p[:-2]):
return True
if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
return True
if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
return True
return False
cache = {}
def isMatch(self, s, p):
if (s, p) in self.cache:
return self.cache[(s, p)]
if not p:
return not s
if p[-1] == '*':
if self.isMatch(s, p[:-2]):
self.cache[(s, p)] = True
return True
if s and (s[-1] == p[-2] or p[-2] == '.') and self.isMatch(s[:-1], p):
self.cache[(s, p)] = True
return True
if s and (p[-1] == s[-1] or p[-1] == '.') and self.isMatch(s[:-1], p[:-1]):
self.cache[(s, p)] = True
return True
self.cache[(s, p)] = False
return False
DP version:
def isMatch(self, s, p):
dp = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
dp[0][0] = True
for i in range(1, len(p)):
dp[i + 1][0] = dp[i - 1][0] and p[i] == '*'
for i in range(len(p)):
for j in range(len(s)):
if p[i] == '*':
dp[i + 1][j + 1] = dp[i - 1][j + 1] or dp[i][j + 1]
if p[i - 1] == s[j] or p[i - 1] == '.':
dp[i + 1][j + 1] |= dp[i + 1][j]
else:
dp[i + 1][j + 1] = dp[i][j] and (p[i] == s[j] or p[i] == '.')
return dp[-1][-1]
class Solution(object):
def isMatch(self, s, p):
# The DP table and the string s and p use the same indexes i and j, but
# table[i][j] means the match status between p[:i] and s[:j], i.e.
# table[0][0] means the match status of two empty strings, and
# table[1][1] means the match status of p[0] and s[0]. Therefore, when
# refering to the i-th and the j-th characters of p and s for updating
# table[i][j], we use p[i - 1] and s[j - 1].
# Initialize the table with False. The first row is satisfied.
table = [[False] * (len(s) + 1) for _ in range(len(p) + 1)]
# Update the corner case of matching two empty strings.
table[0][0] = True
# Update the corner case of when s is an empty string but p is not.
# Since each '*' can eliminate the charter before it, the table is
# vertically updated by the one before previous. [test_symbol_0]
for i in range(2, len(p) + 1):
table[i][0] = table[i - 2][0] and p[i - 1] == '*'
for i in range(1, len(p) + 1):
for j in range(1, len(s) + 1):
if p[i - 1] != "*":
# Update the table by referring the diagonal element.
table[i][j] = table[i - 1][j - 1] and \
(p[i - 1] == s[j - 1] or p[i - 1] == '.')
else:
# Eliminations (referring to the vertical element)
# Either refer to the one before previous or the previous.
# I.e. * eliminate the previous or count the previous.
# [test_symbol_1]
table[i][j] = table[i - 2][j] or table[i - 1][j]
# Propagations (referring to the horizontal element)
# If p's previous one is equal to the current s, with
# helps of *, the status can be propagated from the left.
# [test_symbol_2]
if p[i - 2] == s[j - 1] or p[i - 2] == '.':
table[i][j] |= table[i][j - 1]
return table[-1][-1]
public boolean matchRegex(char[] text, char[] pattern) {
boolean T[][] = new boolean[text.length + 1][pattern.length + 1];
T[0][0] = true;
//Deals with patterns like a* or a*b* or a*b*c*
for (int i = 1; i < T[0].length; i++) {
if (pattern[i-1] == '*') {
T[0][i] = T[0][i - 2];
}
}
for (int i = 1; i < T.length; i++) {
for (int j = 1; j < T[0].length; j++) {
if (pattern[j - 1] == '.' || pattern[j - 1] == text[i - 1]) {
T[i][j] = T[i-1][j-1];
} else if (pattern[j - 1] == '*') {
T[i][j] = T[i][j - 2];
if (pattern[j-2] == '.' || pattern[j - 2] == text[i - 1]) {
T[i][j] = T[i][j] | T[i - 1][j];
}
} else {
T[i][j] = false;
}
}
}
return T[text.length][pattern.length];
}