- Regular Expression Matching
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).
The function prototype should be:
bool isMatch(const char *s, const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "a*") → true
isMatch("aa", ".*") → true
isMatch("ab", ".*") → true
isMatch("aab", "c*a*b") → true
class Solution { public boolean isMatch(String s, String p) { int ls = s.length(), lp = p.length(); boolean[][] dp = new boolean[lp + 1][ls + 1]; dp[0][0] = true; for (int i = 2; i < lp + 1; i++) { if (p.charAt(i - 1) == '') dp[i][0] = dp[i - 2][0]; } for (int i = 1; i < lp + 1; i++) { for (int j = 1; j < ls + 1; j++) { if (s.charAt(j - 1) == p.charAt(i - 1) || p.charAt(i - 1) == '.') dp[i][j] = dp[i - 1][j - 1]; else if (p.charAt(i - 1) == '') if (p.charAt(i - 2) == s.charAt(j - 1) || p.charAt(i - 2) == '.') dp[i][j] = dp[i][j - 1] || dp[i - 1][j] || dp[i - 2][j]; else dp[i][j] = dp[i - 2][j]; } } return dp[lp][ls]; } }
my thoughts:
1. complicated dp:
'' a a a b b c -s
'' 1 0(N) 0(N) 0(N) 0(N) 0(N) 0(N)
a 0 1(Y) 0(Y) 0(Y) 0(N) 0(N) 0(N)
* 1 1(M1) 1(M1) 1(M1) 0(M2) 0(M2) 0(M2)
a 0 1(Y) 1(Y) 1(Y) 0(N) 0(N) 0(N)
. 0 0(Y) 1(Y) 1(Y) 1(Y) 0(Y) 0(Y)
d 0 0(N) 0(N) 0(N) 0(N) 0(N) 0(N)
* 0 0(M2) 1(M2) 1(M2) 1(M2) 0(M2) 0(M2)
c 0 0(N) 0(N) 0(N) 0(N) 0(N) 0(Y)
|
p
'' a a a b c -s
'' 1 0(N) 0(N) 0(N) 0(N) 0(N)
a 0 1(Y) 0(Y) 0(Y) 0(N) 0(N)
* 1 1(M1) 1(M1) 1(M1) 0(M2) 0(M2)
a 0 1(Y) 1(Y) 1(Y) 0(N) 0(N)
. 0 0(Y) 1(Y) 1(Y) 1(Y) 0(Y)
d 0 0(N) 0(N) 0(N) 0(N) 0(N)
* 0 0(M2) 1(M2) 1(M2) 1(M2) 0(M2)
c 0 0(N) 0(N) 0(N) 0(N) 1(Y)
|
p
hold p, check s by chars:
if (Y) s[j] == p[i] or p[i] == '.': dp[i][j] = dp[i-1][j-1];
if (N) s[j] != p[i] and p[i] != '*': dp[i][j] = 0
if (M) p[i] == '*':
if (M1)p[i-1] == s[j] any of the three
if * means 0, dp[i][j] = dp[i-2][j]
if * means 1, dp[i][j] = dp[i-1][j]
if * means >1, dp[i][j] = dp[i][j-1]
if (M2) p[i-1] != s[j]: dp[i][j] = dp[i-2][j]
** as we are checking along the columns more often, let's rotate the matrix for better performance.
my solution:
**********97ms
class Solution(object):
def isMatch(self, s, p):
"""
:type s: str
:type p: str
:rtype: bool
"""
if not p:
return not s
checker = [[False]*(len(p)+1) for i in range( len(s)+1 )]
checker[0][0] = True
for i in range(2,len(checker[0])):
if p[i-1] == '*' and checker[0][i-2]:
checker[0][i] = True
for i in range(1, len(s)+1):
for j in range(1, len(p)+1):
if p[j-1] == '.' or p[j-1] == s[i-1]:
checker[i][j] = checker[i-1][j-1]
elif p[j-1] == '*':
if p[j-2] != s[i-1] and p[j-2] != '.':
checker[i][j] = checker[i][j-2]
else:
checker[i][j] = checker[i][j-2] or checker[i][j-1] or checker[i-1][j]
#print checker
return checker[-1][-1]
my comments:
from other ppl's solution:
1. I think this recursion is not intuitive, 62ms:
class Solution(object):
def dpMatch(self,i,j):
if (i,j) in self.dp:
return self.dp[i,j]
if len(self.p[j:])==0:
return len(self.s[i:])==0
firstmatch=len(self.s[i:])!=0 and self.p[j] in [self.s[i],'.']
if len(self.p[j:])>=2 and self.p[j+1]=='*':
self.dp[i,j]=self.dpMatch(i,j+2) or (firstmatch and self.dpMatch(i+1,j))
return self.dp[i,j]
else:
self.dp[i,j]=firstmatch and self.dpMatch(i+1,j+1)
return self.dp[i,j]
def isMatch(self,s,p):
self.s=s
self.p=p
self.dp={}
return self.dpMatch(0,0)
2. more readable maybe, 55ms:
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)