[LeetCode][python3]0010. Regular Expression Matching

Start the Journey
N2I -2020.03.17

1. A Fast Solution

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        if not p: return not s       
        lvl = {0}
        for i, c in enumerate(p[:-1], 1):
            if not lvl: return False            
            if c == ".":
                if p[i] == "*":
                    lvl = set(range(min(lvl), len(s)+1))
                else: lvl = {j+1 for j in lvl if j < len(s)}
            elif c != "*":
                if p[i] == "*":
                    tmp = set()
                    for j in lvl:
                        while j < len(s) and s[j] == c:
                            j += 1
                            tmp.add(j)
                    lvl.update(tmp)
                else: lvl = {j+1 for j in lvl if j < len(s) and s[j] == c}        
        return len(s) in lvl if p[-1] == "*" else len(s) - 1 in lvl and (s[-1] == p[-1] or "." == p[-1])
 

Explanation:

lvl is a set type with 0 in it initially, which represents “check out s[0]” when it reads the next char from p. lvl will always save the set next chars to be checked, that means the strings before them was covered by the current pit has read. For example, if lvl={3,7} that means s[0:3] and s[0:7] is under cover, but not including s[0:5]. 

The p[i] always points to the following next char by c on the basis of enumrate(p[:-1],1) , the main use of p[i] is to check if the next char of c is "*" .

The for loop will continuously check the string p[:-1] until p[-1] , and leave the last char of p to be checked in the return section.

2. A Clean Solution

class Solution(object):
    def isMatch(self, text, pattern):
        if not pattern:
            return not text
        first_match = bool(text) and pattern[0] in {text[0], '.'}
        if len(pattern) >= 2 and pattern[1] == '*':
            return (self.isMatch(text, pattern[2:]) or first_match and self.isMatch(text[1:], pattern))
        else:
            return first_match and self.isMatch(text[1:], pattern[1:])
 

Explanation:

It is a recursive method. It makes a new branch every time it meets "?*". It is cleaner and easier to understand but cost more time for recursive.

3. My first try

Logically the same as Solution 2, but a much longer code. So I delete it.