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

Leetcode-cn.com/problems/wi…

‘? ‘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”

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:

Input: s = “acdcb” p = “a*c? B “output: false

Java solution

Ideas:

  • Preliminary idea: traversal of P, * N times of backmove (hit follow-up stop), debugging many times a face meng force
  • We decided to split p and use a stack, which holds strings (*,?) separated by P. , “arbitrary string”)
  • Stack pops up to perform string lookup in another string operation
  • Too young to be dead, check out the official solution (some problems still have to be solved first and then optimized, after several hours, still have to supplement while solving the problem)
// Official solution dynamic programming
public boolean isMatch(String s, String p) {
    int m = s.length();
    int n = p.length();
    boolean[][] dp = new boolean[m + 1][n + 1];
    dp[0] [0] = true;
    for (int i = 1; i <= n; ++i) {
        if (p.charAt(i - 1) = =The '*') {
            dp[0][i] = true;
        } else {
            break; }}for (int i = 1; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (p.charAt(j - 1) = =The '*') {
                dp[i][j] = dp[i][j - 1] || dp[i - 1][j];
            } else if (p.charAt(j - 1) = ='? ' || s.charAt(i - 1) == p.charAt(j - 1)) {
                dp[i][j] = dp[i - 1][j - 1]; }}}return dp[m][n];
}
Copy the code

The official solution

Leetcode-cn.com/problems/wi…

  1. Dynamic programming

    Understand the official solution

For letters and? Can be deterministic matches, * matches any character, so there is dynamic programming to reduce repetition, enumerating all cases

A two-dimensional array records whether the current position matches

0.0–> Determine the details — Determine the state transition equation — code master world

  • Time complexity: O(Mn)

  • Space complexity: O(Mn)