题目
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:
-
scould be empty and contains only lowercase lettersa-z. -
pcould be empty and contains only lowercase lettersa-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
难度
Hard
方法1
递归处理
- 如果
text[0] == pattern[0]或者pattern[0] == "."，记作first_match = True，否则first_match = False - 继续处理下一个字符，如果下一个字符不为
*，则处理isMatch(text[1:], pattern[1:]) - 如果
pattern[1] == "*"，如果first_match匹配，则继续看isMatch(text[1:], pattern)是否继续匹配； 如果first_match不匹配，由于*可以表示0个字符，则看isMatch(text, pattern[2:])是否匹配
python代码1
class Solution(object):
def isMatch(self, s, p):
"""
Runtime: 1896ms
:param s: str
:param p: str
:return: bool
"""
first_match = False
if len(s) == 0 and len(p) == 0:
return True
if len(s) > 0 and len(p) > 0:
first_match = p[0] in [s[0], "."]
if len(p) >= 2 and p[1] == "*":
return (first_match and self.isMatch(s[1:], p)) or self.isMatch(s, p[2:])
else:
return first_match and self.isMatch(s[1:], p[1:])
方法2
动态规划，效率更高，能够记下中间结果
递进的思路有些类似于方法1
first_match = True if i < len(s) and (s[i] == p[j] or p[j] == ".") else False
if j + 1 < len(p) and p[j+1] == "*":
dp[(i, j)] = first_match and dp.get((i+1, j), False) or dp.get((i, j + 2), False)
else:
dp[(i, j)] = dp.get((i+1, j+1), False) and first_match
其中dp[(i, j)]表示text[i:],pattern[j:]是否匹配，dp[(0, 0)]即为text，pattern是否匹配的结果, dp[(len(text), len(pattern)] = True
python代码2
class Solution(object):
def isMatch(self, s, p):
"""
Runtime: 112ms
:param s: str
:param p: str
:return: bool
"""
dp = {}
i = len(s)
j = len(p) - 1
dp[(len(s), len(p))] = True
while i >= 0:
j = len(p) - 1
while j >= 0:
first_match = True if i < len(s) and (s[i] == p[j] or p[j] == ".") else False
if j + 1 < len(p) and p[j+1] == "*":
dp[(i, j)] = first_match and dp.get((i+1, j), False) or dp.get((i, j + 2), False)
else:
dp[(i, j)] = dp.get((i+1, j+1), False) and first_match
j -= 1
i -= 1
return dp[(0, 0)] if (0, 0) in dp else False
assert Solution().isMatch("aa", "a") is False
assert Solution().isMatch("aa", "a*") is True
assert Solution().isMatch("ab", ".*") is True
assert Solution().isMatch("aab", "c*a*b") is True
assert Solution().isMatch("mississippi", "mis*is*p*.") is False
