Leetcode – Wildcard match

This is the 25th day of my participation in the genwen Challenge

Topic describes

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:

• sMay be empty and contain only lowercase letters from A to Z.
• pCan be empty and contain only lowercase letters from A to Z, and 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

Their thinking

In a given pattern P, only three types of characters appear:

• Lowercase letters a to Z can match one lowercase letter.
• The question mark? , can match any lowercase letter;
• The asterisk, which matches any string, can be null, i.e. matches zero or any number of lowercase letters.

The match between “lowercase” and “question mark” is certain, and the match between “asterisk” is uncertain, so we need to enumerate all matches. To reduce repeated enumerations, we can use dynamic programming to solve this problem.

We use dp[I][j] to indicate whether the first I characters of string S and the first j characters of pattern P can match. For state transitions, we can consider the JTH character of schema P, pjp_JPj, which corresponds to the ith character of string S, sis_isi:

If pJP_JPJ is lowercase, then sis_ISI must also be the same lowercase, and the state transition equation is:

If PJP_JPJ is a question mark, then there is no requirement for sIS_ISI, and the state transition equation is:

If pJP_JPJ is an asterisk, then again there is no requirement for sis_ISI, but the asterisk can match zero or any number of lowercase letters, so the state transition equation is divided into two cases, with or without the asterisk:

code

C + + code

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size(a);int n = p.size(a); vector<vector<int>> dp(m + 1, vector<int>(n + 1));
        dp[0] [0] = true;
        for (int i = 1; i <= n; ++i) {
            if (p[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[j - 1] = =The '*') {
                    dp[i][j] = dp[i][j - 1] | dp[i - 1][j];
                }
                else if (p[j - 1] = ='? ' || s[i - 1] == p[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1]; }}}returndp[m][n]; }};Copy the code