10. regular expression matching

10. Regular Expression Matching

Original title link ：https://leetcode.cn/problems/regular-expression-matching/

Give you a string s And a character rule p, Please come to realize a support ‘.’ and ‘*’ Regular expression matching .

‘.’ Match any single character
‘*’ Match zero or more previous elements
Match , Is to cover Whole character string s Of , Instead of partial strings .

Example 1：

Input ：s = “aa”, p = “a”
Output ：false
explain ：“a” Can't match “aa” Whole string .
Example 2:

Input ：s = “aa”, p = “a*”
Output ：true
explain ： because ‘*’ Represents the element that can match zero or more preceding elements , The element in front of here is ‘a’. therefore , character string “aa” Can be regarded as ‘a’ I repeated it once .
Example 3：

Input ：s = “ab”, p = “."
Output ：true
explain ：".” Means zero or more can be matched （‘*’） Any character （‘.’）.

Tips ：

1 <= s.length <= 20
1 <= p.length <= 30
s Only from a-z Lowercase letters of .
p Only from a-z Lowercase letters of , As well as the character . and *.
Ensure that characters appear every time * when , All of them are matched with valid characters

Their thinking ：

The problem of dynamic programming , State needs to be defined , Initialization status , Find the state transition equation , See the references for details .

Code implementation ：

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        #  Definition dp[i][j]: s Before i Characters and p Before j Whether characters match 
        #  So the value is True  perhaps  False

        m, n = len(s), len(p)

        #  One more row, one more column , Represents an empty string s and p
        dp = [[False] * (n + 1) for _ in range(m + 1)]

        #  assignment dp The border 
        #  Space transfer energy matching empty string , So it is True
        dp[0][0] = True
        for j in range(1, n + 1):
            # p[j - 1] Can match p[j - 2]
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                #  If the current character matches or p The current character of is a universal character '.'
                if s[i - 1] == p[j - 1] or p[j - 1] == '.':
                    #  Whether the current character matches or not is the same as looking forward to a character match 
                    dp[i][j] = dp[i - 1][j - 1]
                #  If p The current character of is '*'
                elif p[j - 1] == '*':
                    #  If s The current character of does not match p Is equal to the previous character of the current character of 
                    #  also p The previous character of the current character of is not a universal character '.'
                    if s[i - 1] != p[j - 2] and p[j - 2] != '.':
                        #  When it matches and goes p The first two characters are the same 
                        dp[i][j] = dp[i][j - 2]
                    else:
                        dp[i][j] = dp[i][j-2] | dp[i-1][j]
        
        return dp[m][n]

reference ：
https://leetcode.cn/problems/regular-expression-matching/solution/by-flix-musv/