[LeetCode]10. Regular Expression

题目

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

难度

Hard

方法1

递归处理

1. 如果text[0] == pattern[0]或者pattern[0] == "."，记作first_match = True，否则first_match = False
2. 继续处理下一个字符，如果下一个字符不为*，则处理isMatch(text[1:], pattern[1:])
3. 如果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