9/16 每日一題(正則表達式)

Given an input string s and a pattern p, implement regular expression matching with support for '.' and '*' where:

• '.' Matches any single character.​​​​
• '*' Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

 

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 preceding 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 (.)".

 

Constraints:

• 1 <= s.length <= 20
• 1 <= p.length <= 20
• s contains only lowercase English letters.
• p contains only lowercase English letters, '.', and '*'.
• It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

import re

class Solution:

    def isMatch(self, s: str, p: str) -> bool:

        res=[]

        if '*' in p:

            c=0

            for n,i in enumerate(p):

                if i=='*' and p[n-1]=='*':

                    '記住部必要的索引'

                    res.append(n)

                    c=1

            if c:

               

                p=p[:res[0]]+p[res[-1]+1:]

                print(p)

       

                   

                       

        reg=re.compile(p)

        res=reg.findall(s)

        return s in res

------------------------------------

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        # tokenize
        tkns = []
        for i, c in enumerate(p):
            star = (p[i + 1] == '*') if i < len(p) - 1 else False
            if star:
                tkns.append('*' + c)
            elif c == '*':
                pass
            else:
                tkns.append(c)
        # end tokenize
        okays = [-1]
        for t in tkns:
            if not okays:
                return False
            if t == '.':
                okays = [i + 1 for i in okays if i + 1 < len(s)]
                continue
            if t[0] == '*':
                if t[1] == '.':
                    okays = list(range(okays[0], len(s)))
                    continue
                crepeat = t[1]
                buff = []
                for iokay, i in enumerate(okays):
                    stop = okays[iokay + 1] if iokay < len(okays) - 1 else len(s)
                    for j in range(i, stop):
                        if j == i or s[j] == crepeat:
                            buff.append(j)
                        else:
                            break
                okays = buff
                continue
            # if t = 'a'
            okays = [i + 1 for i in okays if i + 1 < len(s) and s[i + 1] == t]
        return 0 < len(okays) and okays[-1] == len(s) - 1

-----------------------------------------

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        cache = {}

        def dfs(i, j):
            if (i, j) in cache:
                return cache[(i, j)]
            if i >= len(s) and j >= len(p):
                return True
            if j >= len(p):
                return False
            
            match = (i < len(s)) and (s[i] == p[j] or p[j] == ".")
            if (j + 1) < len(p) and p[j + 1] == "*":
                # don't use the start\
                cache[(i, j)] = (dfs(i, j + 2) or
                    (match and dfs(i + 1, j))) # use the *
                return cache[(i, j)]
            
            if match:
                cache[(i, j)] = dfs(i + 1, j + 1)
                return cache[(i, j)]
            cache[(i, j)] = False
            return False
        return dfs(0, 0)