This is the fourth day of my participation in the wenwen Challenge

Topic describes

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘? ‘ and ‘*’ where:

Given a string (s) and a character pattern (p), implement a system that supports ‘? The wildcard of ‘and ‘*’ matches.

  • '? ' Matches any single character.'? 'Can match any single character.
  • The '*' Matches any sequence of characters (including the empty sequence).The '*'Can match any string (including empty string)

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

A match is successful only if the two strings match exactly

Example 1:

Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".
Copy the code

Example 2:

Input: s = "aa", p = "*"
Output: true
Explanation: '*' matches any sequence.
Copy the code

Example 3:

Input: s = "cb", p = "? a" Output: false Explanation: '? ' matches 'c', but the second letter is 'a', which does not match 'b'.Copy the code

Example 4:

Input: s = "adceb", p = "*a*b"
Output: true
Explanation: The first '*' matches the empty sequence, while the second '*' matches the substring "dce".
Copy the code

Example 5:

Input: s = "acdcb", p = "a*c? b" Output: falseCopy the code

Constraints:

  • 0 < =s.length.p.length< = 2000
  • s contains only lowercase English letters.
  • p contains only lowercase English letters, '? ' or The '*'.

Their thinking

More classical dynamic programming solution

According to the question, ‘? The matching pattern of ‘and’ lowercase ‘is deterministic. The undeterministic factor is the matching of ‘*’, which can be empty or any number of arbitrary characters.

Use dp[I][j]dp[I][j]dp[I][j]dp[I][j] to indicate whether the first I characters of string s and the first JJJ characters of pattern P can match. When making state transitions, you can consider the JJJ character pJP_JPj of pattern P, which corresponds to the iii character sis_isi in string S

If pJP_JPJ is lowercase, then sis_ISI must also be the same lowercase, and the state transition equation is


d p [ i ] [ j ] = ( s i with p j The same ) Sunday afternoon d p [ i – 1 ] [ j – 1 ] Dp [I][j]=(s_i = p_j) \land DP [i-1][j-1]

If PJP_JPJ is a question mark, then there is no requirement for SIS_ISI, and the state transition equation is


d p [ i ] [ j ] = d p [ i – 1 ] [ j – 1 ] dp[i][j]=dp[i-1][j-1]

If pJP_JPJ is an asterisk, then again there is no requirement for sis_ISI, but the asterisk can match zero or any number of lowercase letters, so the state transition equation is divided into two cases, using or not using the asterisk


d p [ i ] [ j ] = d p [ i ] [ j – 1 ] ∨ d p [ i – 1 ] [ j ] dp[i][j]=dp[i][j-1]\lor dp[i-1][j]

Next, we need to determine the boundary case dp[0][0]=Truedp[0][0]=Truedp[0][0]=True, that is, when both string S and mode P are empty, the match is successful;

Falsedp[I][0]=Falsedp[I][0]=Falsedp[I][0]=Falsedp[I][0]=Falsedp[I][0]=False;

Dp [0][j]dp[0][j]dp[0][j] dp[0][j]dp[0][j]dp[0][j] is true only if the first JJJ characters of pattern P are all asterisks.

code

Python code

class Solution:
    def isMatch(self, s: str, p: str) - >bool:
        m, n = len(s), len(p)

        dp = [[False] * (n + 1) for _ in range(m + 1)]
        dp[0] [0] = True
        for i in range(1, n + 1) :if p[i - 1] = =The '*':
                dp[0][i] = True
            else:
                break
        
        for i in range(1, m + 1) :for j in range(1, n + 1) :if p[j - 1] = =The '*':
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j]
                elif p[j - 1] = ='? ' or s[i - 1] == p[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                
        return dp[m][n]
Copy the code