Subject to introduce

Force buckle 44 questions: leetcode-cn.com/problems/wi…

Analysis of the

Let’s look at a table like this

Where, the horizontal axis is string s, and the vertical axis is pattern P, the meaning of the (m,n) grid in this table is: whether the whole paragraph [p from position 0 to position M] can match the whole paragraph [s from position 0 to position N], that is, if the following position in the table stores T(True) : It says, “ADCB” and “A * B” match, and you don’t care what happened, you just know that these two match, and that’s why dynamic programming is so good, right

Okay, let’s go back to where we started. So how do we walk happily on this chart?

I put a T in the position (START,START), that’s where we START walking, and we can only go down at T

So what direction can I go from T?

This is a string matching problem, so string matching can’t go backwards, you can’t go backwards in “abcde”, like from E to D

This “can’t go backwards” rule is reflected in our table, that is, can only go to the bottom right corner, you can elaborate on why (right, down is also possible, we will talk about later; Anyway, the top left, top left corner is impossible because you can’t go backwards!)

If WE go to the bottom right, let me give you an example, if we start from where we started, if we go to the bottom right, we go to (a,a), and we find that these two new letters match, we record a “T” here.

It’s that simple. What if there were only letters in p and S, no “and “? These two things, every time you go from one of the original T cells to the bottom right corner, if the two new letters match, you can record a T in the new cell. Tap the board again: you can only go from the T cell, if there is nothing in a cell (False), you can’t start from there. Let’s talk about “and “?

The reason WHY I call this table a board in the title is because I think it is like a chess game. We know that each piece in Chinese chess has different functions. For example, the pawn can only move one square at a time, but the rook can move any square at a time, and some pieces can jump

In our case, ordinary letters such as A and B are like soldiers. When they meet, they can only move down one space to the right. After this step, T can be recorded by judging whether the two newly introduced letters match.

And “*” and “?” Characters with special skills!

Role: “” Stunt: Bulldoze Road Description: If this row is “”, you can start from any T in the previous row and bulldoze any road in this row down and right example:

Everywhere he went, he lay flat

Why “*” can go straight down from T: Asterisks can match empty strings

The reason “*” can level all the right side of the road: asterisks can match strings of any length and you can check both reasons. Talking about another tough character “?” Before we do that, let’s take a couple more steps just to reinforce what we already know. Next, we encountered a b in pattern, which is a common letter, so we can only go to the lower right corner from a T in the previous line, and T can only be recorded by matching letters, so we found that we can take the following two steps:

Role: “?” Stunt: Leopard cat for Prince Description: If this line is “? , a certain T from the previous line can only go to the lower right corner, but does not need to match the letter to record T example:

As long as you have the T, you can go one space to the bottom right, you don’t care about the letters. Here’s the prince “E” by the tanuki? Offset the

Wow, all of a sudden came to the last grid, small soldiers walk a grid can liao

To determine a successful match, just look at one grid!! If the bottom right corner is T, it’s a match, and we don’t care what happened before, so we’ve got it,

For example, cases like this (I replaced the last letter of the S with an E) are unsuccessful:

The code is as follows:

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        boolean[][] f = new boolean[m + 1][n + 1];
        
        f[0] [0] = true;
        for(int i = 1; i <= n; i++){
            f[0][i] = f[0][i - 1] && p.charAt(i - 1) = =The '*';
        }
        
        for(int i = 1; i <= m; i++){
            for(int j = 1; j <= n; j++){
                // Move directly to the lower right corner
                if(s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) = ='? '){
                    f[i][j] = f[i - 1][j - 1];
                }
                if(p.charAt(j - 1) = =The '*'){
                    f[i][j] = f[i][j - 1] || f[i - 1][j]; }}}returnf[m][n]; }}Copy the code