Topic describes

Their thinking

  • There are two main solutions to this problem, namely recursive backtracking and dynamic programming. Considering that dynamic programming is difficult to understand, this paper adopts recursive backtracking to explain the problem, and the steps are as follows:

1. Check whether the string p is empty. If so, continue to check whether the string S is empty

  • We first need to understand exactly what character S and character P mean. Character S represents the string to be matched, and character P represents our matching pattern
  • If the matching pattern is empty, we need to look at whether the matching character s is empty. If both are empty, it means that empty matches empty and returns true. If p is empty, but s is not empty, it means that empty matches non-empty and must be false.
if (p.length === 0) {
    if (s.length === 0) {
        return true;
    } else {
        return false; }}Copy the code

2. Check whether the first character can be successfully matched if the string s is not empty

  • Why match if s is not empty?

A: Because if s is empty, it makes no sense to match the first character. If s is empty and can go here, p is not empty. Otherwise, it can’t go to the second step and return.

  1. The match is successful if the first character of S is equal to the first character of P, or if the first character of P is “.”.
  2. Determine the length of the string p, at this point there are two situations, one is less than 2, one kind is greater than or equal to 2, if less than 2, we don’t need to figure out whether the current character p of the second character *, will directly s removes the first element and p removes the first element, into a recursive function to continue to judge, if greater than or equal to 2, it is necessary to continue to judge, We to determine character of the second character is p *, if the second is the * there are two situations, one is the * representative characters appeared in front of zero, the other is a situation in which the characters appear in front of The Times, at this point we’re going to points of discussion, if represents the zero, will be constant and p s get rid of the first two characters, recursive functions, If it’s multiple, let’s say it’s one first, drop s from the top, and keep going with p.
  3. If the length of the string p is less than 2, the first element is the same because of the restriction of the previous condition, we just remove the first element of S and P respectively and continue to enter the recursion. The end condition helps us continue to judge.
  4. If the string s is empty, or the first character not match, we first determine the length of the p, if p is less than 2, the length of the current element, behind no * again, so direct returns false, if the length of p is greater than or equal to 2, continue to figure out whether the second element of p *, if it is, will be the same, s P continues recursively by removing the first two elements, and returns false if the second element is not *.

The problem solving code

var isMatch = function (s, p) {
    // Check whether mode p is empty. If so, check whether s is empty
    if (p.length === 0) {
        if (s.length === 0) {
            return true;
        } else {
            return false; }}// Determine if the first character matches
    if(s.length ! = =0 && (s[0] === p[0] || p[0= = ='. ')) {
        // The first character is matched
        if (p.length >= 2) {
            // Check if the second character is *
            if (p[1= = =The '*') {
                return isMatch(s, p.slice(2)) || isMatch(s.slice(1), p)
            } else {
                return isMatch(s.slice(1), p.slice(1)); }}else {
            return isMatch(s.slice(1), p.slice(1)); }}else {
        if (p.length >= 2) {
            if (p[1= = =The '*') {
                return isMatch(s, p.slice(2));
            } else {
                return false; }}else {
            return false; }}};Copy the code

Conclusion (this topic gives us the enlightenment of thinking)

  • Learn how to solve multiple boundary condition problems by recursive backtracking
  • Don’t be anxious. Don’t give up. Think carefully and you will always find a solution.