Cracking LeetCode: 10. Regular Expression Matching
May
10
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
‘*’ 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
Thought:
DP:
f[m][n] means s[0,..,m-1] matches p[0,…,n-1]
- If p[n-1] !=’*’, then f[m][n] = s[m-1]==p[n-1] or f[m-1][n-1]
- If p[n-1] == ‘*’, denotes p[n-2] with x, then
- (“x*” repeats 0 times to match empty) f[m][n] = f[m][n-2]
- (“x*” repeats >=1 times to match “x*x”) f[m][n] = f[m-1][n] and s[n-1] == x
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution(object): def isMatch(self, s, p): """ :type s: str :type p: str :rtype: bool """ f = [[0]*(len(p)+1) for _ in range(len(s)+1)] f[0][0] = True for i in range(1,len(s)+1): f[i][0] = False #j>1 is pretty neat since f[0][1] = False for j in range(1,len(p)+1): f[0][j] = j>1 and p[j-1]=='*' and f[0][j-2] for i in range(1,len(s)+1): for j in range(1,len(p)+1): if p[j-1] != '*': f[i][j] = (p[j-1]==s[i-1] or '.'==p[j-1]) and f[i-1][j-1] else: f[i][j] = j>1 and (f[i][j-2] or (p[j-2]==s[i-1] or '.'==p[j-2]) and f[i-1][j]) return f[len(s)][len(p)] |
Reference:
Comments
Comments are closed.