LeetCode10. Regular Expression Matching

题目：

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".

思路一：

可以从模式字符串p来考虑这个问题，情况有三种：

如果p为空，则s为空，匹配成功；s为不空，匹配失败；

如果p的长度为1，或者p的第二个字符不为'*'，则只需要考虑p的第一个字母和s的匹配；

如果p的第二个字符为'*'，则需要考虑p的前两个字母的组合对s的消减。

迭代进行着三步，可以得出匹配结果。代码如下：

 1 class Solution(object):
 2     def isMatch(self, s, p):
 3         if not p:
 4             return not s
 5         if len(p) == 1 or p[1] != '*':
 6             if not s or (p[0] != s[0] and p[0] != '.'):
 7                 return False
 8             else:
 9                 return self.isMatch(s[1:], p[1:])
10         else:
11             i, length = -1, len(s)
12             while i < length and (i < 0 or s[i] == p[0] or p[0] == '.'):
13                 if self.isMatch(s[i + 1:], p[2:]):
14                     return True
15                 i += 1
16             return False

假设s的长度为n，p的长度为m。考虑到第三中情况下的多种可能性，时间复杂度最好为O(min(m, n))即没有'*'，大家冲上来一通匹配，其中一个匹配到头，问题结束，所需的时间复杂度是线性的；最坏的情况是p中‘*’符号很多，我们要一个一个去跳着匹配s中的字符,而每一跳又会生出多种可能性，这可以转化为“减绳子求最大乘积问题”，对应的时间复杂度为O(3^(n/3))。可以看到，这种解法的时间复杂度可以很高。空间复杂度为O(min(n^2, m^2)).在LeetCode的测试用例上，这种解决方案耗时1797ms。

思路二：

考虑用动态规划解决这个问题，以节省时间。假设我们已经知道s中[0, 1, 2, ..., i - 2]和p中[0, 1, 2, ..., j - 2]是否匹配，接下来我们考虑加入s[i - 1]和p[j - 1]后的关系。具体可由p[j - 1]和p[j - 2]的符号类别决定。此种解法的时间复杂度为O(mn),空间复杂度为O(mn)。在时间复杂度上比思路一低很多。此种解法耗时仅97ms。具体代码如下：

class Solution(object):
    def isMatch(self, s, p):
        dp = [[False for _j in range(len(p) + 1)] for _i in range(len(s) + 1)]
        dp[0][0] = True
        for cj in range(2, len(p) + 1):
            if p[cj - 1] == '*':
                dp[0][cj] = dp[0][cj - 2]
        for ri in range(1, len(s) + 1):
            for cj in range(1, len(p) + 1):
                if p[cj - 1] == '.':
                    dp[ri][cj] = dp[ri - 1][cj - 1]
                elif p[cj - 1] == '*':
                    if p[cj - 2] == s[ri - 1] or p[cj - 2] == '.':
                        dp[ri][cj] = dp[ri - 1][cj] or dp[ri - 1][cj - 2] or dp[ri][cj - 2]
                    else:
                        dp[ri][cj] = dp[ri][cj - 2]
                else:
                    dp[ri][cj] = s[ri - 1] == p[cj - 1] and dp[ri - 1][cj - 1]
        return dp[len(s)][len(p)]