Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”

44. Wildcard matching

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

'? 'can match any single character. '*' can match any string (including empty strings). A match is successful only if the two strings match exactly.Copy the code

Description:

S may be empty and contain only lowercase letters from A to Z. P may be empty and contain only lowercase letters from A to Z, as well as characters? And *.Copy the code
Example 1: Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa". Example 2: Input: s = "aa" p = "*" Output: true Description: '*' can match any string. Example 3: Enter: s = "cb" p = "? A "output: false Explanation: '? 'matches 'c', but the second 'a' does not match 'b'. Example 4: Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty string and the second '*' matches the string "dCE ". Example 5: Enter: s = "acdcb" p = "a*c? B "output: falseCopy the code

To define an array

Dp [I][j] indicates whether the first I characters of S match the first J characters of P

Initialize the

Because * matches an empty string, it matches an empty string as long as the first part of s is consecutive *

State transition

  1. p.charAt(j-1)==’? ‘||p.charAt(j-1)==s.charAt(i-1)

2. P.charat (J-1)==’*’

  • * can be taken as an empty string, so it can be escaped from dp[I][j-1]
  • When traversing i-1, * may become a wildcard string, such that i-1 of S matches j of P, whereas * can match any string, so we can modify the wildcard string so that the i-th character is in the wildcard string, and the result is passed from dp[i-1][j]

code

class Solution {
    public boolean isMatch(String s, String p) {

        int n=s.length(),m=p.length();
        boolean[][] dp=new boolean[n+1][m+1];
        dp[0] [0] =true;
        for(int i=1; i<=m; i++) {if(p.charAt(i-1) = =The '*')
            {
                dp[0][i]=true;
            }else break;
         }
        for(int i=1; i<=n; i++)for(int j=1; j<=m; j++) {if(p.charAt(j-1) = ='? '||p.charAt(j-1)==s.charAt(i-1))
                dp[i][j]=dp[i-1][j-1];
                else if(p.charAt(j-1) = =The '*')
                {
                dp[i][j]=dp[i-1][j] | dp[i][j-1]; }}returndp[n][m]; }}Copy the code