This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

This is a 44. Wildcard match on LeetCode, difficulty is difficult.

Tag: “Linear DP”

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.

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 *.

Example 1:

Input: s = "aa" p = "a" Output: false Description: "A" cannot match the entire string "aa".Copy the code

Example 2:

Input: s = "aa" p = "*" Output: true Description: '*' can match any string.Copy the code

Example 3:

Enter: s = "cb" p = "? A "output: false Explanation: '? 'matches 'c', but the second 'a' does not match 'b'.Copy the code

Example 4:

Input: s = "adceb" p = "*a*b" Output: true Explanation: The first '*' matches the empty string and the second '*' matches the string "dCE ".Copy the code

Example 5:

Input: s = "acdcb" p = "a*c? B "output: falseCopy the code

Dynamic programming

This problem is similar to 10. Regular expression matching.

But compared to number 10, it’s a little easier.

For the string p, there are three types of characters:

  • Common characters: must match the characters at the same position in S

  • ‘? ‘: can match any character at the same position in s

  • ‘*’ : Can match any string

When a character like ‘*’ appears, is it 0, 1, or 2 characters?

This problem can be solved using dynamic programming:

  • State definition: f(I,j) stands for considering whether the substring ending in I in S matches the substring ending in j in P. That is, the final result we want is f[n][m].

  • State transfer: that is, we need to consider how f(I,j) is obtained. Previously, p has three kinds of characters, so the state transfer here also needs to be discussed in three cases:

    1. P [j] is a common character: the matching condition is that the preceding character matches, and the ith character in S is the same as the JTH bit in P. That is, f(I,j) = F (i-1, J-1) &&s [I] == P [j].

    2. P [j] is ‘.’ : the matching condition is that the preceding character matches. The ith character in s can be any character. That is, f(I,j) = f(I – 1, j-1) &&p [j] == ‘.’.

    3. P [j] is ‘*’ : can match any length of characters, 0 characters, 1 characters, 2 characters

      3.1. When the match is 0: f(I,j) = f(I, j-1)

      3.2. When the match is 1: f(I,j) = f(i-1, J-1)

      3.3. When the match is 2: f(I,j) = f(i-2, J-1)

      .

      3. K. When matching k: f(I,j) = f(i-k, j-1)

So for p[j] = ‘*’, f(I, j) = true requires only one of the cases to be true. The relationship between states is “or” :


f [ i ] [ j ] = f [ i ] [ j – 1 ] ∣ ∣ f [ i – 1 ] [ j – 1 ] ∣ ∣ . . . ∣ ∣ f [ i – k ] [ j – 1 ] ( i > = k ) f[i][j] = f[i][j – 1] || f[i – 1][j – 1] || … || f[i – k][j – 1] (i >= k)

Does that mean we need to enumerate k cases?

It doesn’t. For this kind of problem, we can usually simplify it by algebraically substituting I – 1 into the formula above:


f [ i – 1 ] [ j ] = f [ i – 1 ] [ j – 1 ] ∣ ∣ f [ i – 2 ] [ j – 1 ] ∣ ∣ . . . ∣ ∣ f [ i – k ] [ j – 1 ] ( i > = k ) f[i – 1][j] = f[i – 1][j – 1] || f[i – 2][j – 1] || … || f[i – k][j – 1] (i >= k)

It can be found that f[i-1][j] is the same as f[I][j] in f[I][j], so there are:


f [ i ] [ j ] = f [ i ] [ j – 1 ] ∣ ∣ f [ i – 1 ] [ j ] ( i > = 1 ) f[i][j] = f[i][j – 1] || f[i – 1][j] (i >= 1)

PS. In fact, similar derivation, I in10. Regular expression matchingI’ve done that, and the derivation of problem 10 also involves the notion of equivalence, so I highly recommend that you review it. If you can figure out the whole process of number 10, it’s a little Case.

Coding details:

  1. Through the above derivation, you will find that there are quite a few “backcheck” operations designed (i.e. traversal toiBit, check backi - 1Etc.), so we can apply the sentry technique to this problem by inserting the sentry at the head of both strings
  2. forp[j] = '.' 和 P [j] = Common characterWant to betrueIn fact, there are common conditionsf[i - 1][j - 1] == trueSo you can do it all together

Code:

class Solution {
    public boolean isMatch(String ss, String pp) {
        int n = ss.length(), m = pp.length();
        // Trick: Insert a space in the header of the character to get a char array that starts at 1 and makes f[0][0] = true, which can be rolled down
        ss = "" + ss;
        pp = "" + pp;
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();
        // f(I,j) indicates whether characters 1 to I in s and 1 to j in p match
        boolean[][] f = new boolean[n + 1][m + 1];
        f[0] [0] = true;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (p[j] == The '*') {
                    f[i][j] = f[i][j - 1] || (i - 1> =0 && f[i - 1][j]);
                } else {
                    f[i][j] = i - 1> =0 && f[i - 1][j - 1] && (s[i] == p[j] || p[j] == '? '); }}}returnf[n][m]; }}Copy the code
  • Time complexity:nsaidsThe length of themsaidpThe length of theta, totaln * mA state. Complexity of
    O ( n ∗ m ) O(n * m)
  • Spatial complexity: Two dimensional arrays are used to record results. The complexity is O(n∗m)O(n * m)O(n∗m)

Again, dynamic programming is essentially enumeration (non-repeating violence enumeration), so its complexity is easy to analyze, as many times as the states are evaluated.

The last

This is the 44th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.