--

leetcode 010: regular expression matching

https://leetcode.com/problems/regular-expression-matching/

---

---

problem:

---

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

---

---

start code (c++)

---

 
class Solution {
public:
    bool isMatch(string s, string p) {
        
    }
};

---

---

solution:

我的思路：
这里我用 python 来实现了，主要是 python 的对于字符串的操作更加方便一点，当然下面的代码也可以很轻松改写成 C++ 格式的。
递归算法的问题在于，有一些 substr 我们会反复计算是否 match。 我们可以利用动态规划，把已经计算出来的 substr是否match，用一个dict 记录下来。

---

class Solution:
    def isMatch(self, s: 'str', p: 'str') -> 'bool':
        print('s='+s+', p='+p)
        if len(p) == 0:
            return len(s) == 0

        if len(p) >= 2 and p[1] == '*':
            if p[0] == '.':
                # pattern of '.*'
                if len(s) == 0:
                    return self.isMatch('', p[2:])
                else:
                    for i in range(len(s)+1):
                        if self.isMatch(s[len(s)-i  : ], p[2:]):
                            return True
                return False
            else:
                # pattern of 'x*'
                x = p[0]
                i = 0
                # first calculate the max heading x in s
                if len(s) == 0:
                    return self.isMatch('', p[2:])
                else:
                    xs = 0
                    for i in range(len(s)):
                        if s[i] == x:
                            xs +=1
                        else:
                            break
                    for i in range(xs, -1, -1):
                        if self.isMatch(s[i:], p[2:]):
                            return True
                return False
        else:
            # consider one char matching
            if p[0] == '*':
                # not valid pattern
                return False
            elif p[0] == '.':
                return len(s) > 0 and self.isMatch(s[1:], p[1:])
            else:
                # match for a-z
                return len(s) > 0 and s[0] == p[0] and self.isMatch(s[1:], p[1:])
        return False

solution 2: 这个的算法复杂度是： N*M，N 和 M 为 str 和 pattern 的长度

class Solution(object):
    def isMatch(self, text, pattern):
        dp = [[False] * (len(pattern) + 1) for _ in range(len(text) + 1)]

        dp[-1][-1] = True
        for i in range(len(text), -1, -1):
            for j in range(len(pattern) - 1, -1, -1):
                first_match = i < len(text) and pattern[j] in {text[i], '.'}
                if j+1 < len(pattern) and pattern[j+1] == '*':
                    dp[i][j] = dp[i][j+2] or first_match and dp[i+1][j]
                else:
                    dp[i][j] = first_match and dp[i+1][j+1]

        return dp[0][0]

---