“This is the 25th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

1. Title Description

Implement a function to match regular expressions including ‘.’ and ‘*’.

  1. The character ‘.’ in the pattern represents any character
  2. The character ‘*’ in the pattern means that the character preceding it can occur any number of times including zero.

In this case, matching means that all characters in a string match the entire pattern. For example, the string “aaa” matches the patterns “A.a” and “ab*ac*a”, but not “aa.a” and “ab*a”.

Data range:

  1. STR contains only lowercase letters from A to Z.
  2. Pattern contains only lowercase letters from A to Z and the characters. And *. There is no consecutive ‘*’.
  3. 0 or less STR. Length 26 or less
  4. 0 or less the pattern. The length of 26 or less

Second, the problem solving

The difficulty in implementing regular matching in this case lies in the processing of *, if there is no *, then we only need to compare the past by bit, if there is a mismatch of characters or strings and the length of the regular expression is inconsistent, return false, where. Discard them as wildcards in the condition judgment.

So let’s assume there’s no *, and let’s try to solve this problem.

Suppose you have the string ABC and the regular expression A.c.

The method we use is to determine whether the first digit of the two is equal, where the first digit is both a, if the condition is met, then we continue to determine, b! =., but. Make it pass judgment alone.

At this point we have the result of two strings matching successfully, i.e. a matches a and A. Match ab, keep going and it’s not hard to get a.C matches ABC. It is not hard to see that judging regular matches is a recursive process, which is developed from a pair of successfully matched strings and regular expressions.

This conclusion is also valid when matching in reverse order, and the implementation code of reverse order is as follows:

func match( str string ,  pattern string ) bool {
    if len(str) ! =len(pattern) {
        return false
    }
    if len(str) == 0 {
        retrun true
    }
    if str[len(str)- 1] == pattern[len(pattern)- 1] || pattern[len(pattern)- 1] = ='. ' {
        return match(str[:len(str)- 1], pattern[:len(pattern)- 1])}return false
}
Copy the code

If the string is not the same length as the regular expression, the mismatch cannot be detected immediately. If the string is not the same length as the regular expression, the mismatch cannot be detected immediately.

Since * is used to match the preceding character, using reverse order matching simplifies our processing.

If the end value of the regular expression is *, the special treatment for * will be entered:

  1. We can try to put*Use the remaining regular expression to continue matching the string, and return true if the match succeeds. If no match is found, false cannot be returned immediately, and you need to go to the next step.
  2. We can use*The preceding characters match the last character of the string. If a mismatch occurs, return false. If they match, they consume it*Matches the previous element and the last element of the string, and continues the match, for example:
Abb * * = abb* * = abb* * = abb* * = abb* * = abb* * = abb* * = abb* * = abb* * = abb* * = abb* * Return true 3. Abb and AB * = 2, abb and AB * = 2, abb and AB * = 2, abb and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB and AB * = 2, ABB Now I'm going to match bb with b star and I'm going to be left with a and A, which obviously match, and return trueCopy the code

Thus, the realization encoding of * matching is as follows:

    if pattern[len(pattern)- 1] = =The '*' {
        if match(str[:len(str)], pattern[:len(pattern)2 -]) {
            // Return true if the character preceded by * is discarded
            return true
        }
        // Use n as the remaining length of the string, as if the first character is 1-n
        for i := 1; i <= len(str); i++ {
            if str[len(str)-i] == pattern[len(pattern)2 -] || pattern[len(pattern)2 -] = ='. ' {
                // Loop to check whether STR matches the end of pattern
                // If it matches, it tries to continue matching the rest of the string
                if match(str[:len(str)-i], pattern[:len(pattern)2 -]) {
                    // Return true if matched
                    return true
                }
                // If there is no match, extend the search
            } else {
                // There is no need to continue if the last character does not match
                return false}}// All possible attempts are made but no match returns false
        return false
    }
Copy the code

Due to the addition of *, the boundary conditions used before also need to be modified. The influence of * in the regular expression should also be considered, and the complete implementation code is as follows:

func match( str string ,  pattern string ) bool {
    // write code here
    // 1. The string has been matched to see if there are any characters other than *
    if len(str) == 0 {
        for i := len(pattern) - 1; i >= 0; i-- {
            ifpattern[i] ! =The '*' {
                return false
            } else {
                // The * is skipped one bit
                i--
            }
        }
        return true
    }
    // 2. The string is not matched yet
    if len(pattern) == 0 {
        return false
    }
    
    * * * * * * * * * * * * * * * * *
    if pattern[len(pattern)- 1] = =The '*' {
        if match(str[:len(str)], pattern[:len(pattern)2 -]) {
            // Return true if the character preceded by * is discarded
            return true
        }
        // Use n as the remaining length of the string, as if the first character is 1-n
        for i := 1; i <= len(str); i++ {
            if str[len(str)-i] == pattern[len(pattern)2 -] || pattern[len(pattern)2 -] = ='. ' {
                // Loop to check whether STR matches the end of pattern
                // If it matches, it tries to continue matching the rest of the string
                if match(str[:len(str)-i], pattern[:len(pattern)2 -]) {
                    // Return true if matched
                    return true
                }
                // If there is no match, extend the search
            } else {
                // There is no need to continue if the last character does not match
                return false}}// All possible attempts are made but no match returns false
        return false
    }
    
    // The end of the same or any match match substring
    if str[len(str)- 1] == pattern[len(pattern)- 1] || pattern[len(pattern)- 1] = ='. ' {
        return match(str[:len(str)- 1], pattern[:len(pattern)- 1])}Return false if the last character does not match the condition
    return false
}
Copy the code