Leetcode 44. Wildcard Matching

Given an input string (s) and a pattern (p), implement wildcard pattern matching with support for ‘?’ and ‘*’.

‘?’ Matches any single character.
‘*’ Matches any sequence of characters (including the empty sequence).
The matching should cover the entire input string (not partial).

Note:

s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like ? or *.
Example 1:

Input:
s = “aa”
p = “a”
Output: false
Explanation: “a” does not match the entire string “aa”.
Example 2:

Input:
s = “aa”
p = “*”
Output: true
Explanation: ‘*’ matches any sequence.
Example 3:

Input:
s = “cb”
p = “?a”
Output: false
Explanation: ‘?’ matches ‘c’, but the second letter is ‘a’, which does not match ‘b’.
Example 4:

Input:
s = “adceb”
p = “*a*b”
Output: true
Explanation: The first ‘*’ matches the empty sequence, while the second ‘*’ matches the substring “dce”.
Example 5:

Input:
s = “acdcb”
p = “a*c?b”
Output: false
解析：
通配符匹配，这里?匹配一个字符，*匹配一个序列。与正则表达式匹配有些不同。
解法1:双指针法
分别定义两个指针sp和pp分别指向字符和pattern，然后分情况进行判断，如果对应位置的字符相等或者pattern在pp处的字符为?则两个指针分别递增；如果pattern当前位置为*，则定义star_index记录pattern的位置，同时定义match定义对应匹配位置的字符下标。如果star_index不为-1.表示上一个位置是*，字符指针sp进行递增，否则则返回false,如果pattern有剩余，且均为*则直接递增pp，最后判断pp与pattern长度是否相等。
具体代码如下：

class Solution {
public:
    bool isMatch(string s, string p) {
        int sp = 0;//指向字符的指针
        int pp = 0;//指向pattern的指针
        int match = 0;//匹配*的字符的位置
        int star_index = -1;//pattern中*的位置
        while(sp < s.size())
        {
            if(pp < p.size() && (s[sp] == p[pp] || p[pp] == '?'))
               {
                   sp ++;
                   pp ++;
               }else if(pp < p.size() && p[pp] == '*')
               {
                   star_index = pp;
                   match = sp;
                   pp ++;
               }else if(star_index != -1)
               {
                   pp = star_index +1;
                   match ++;
                   sp = match;
               }else
                    return false;
        }
        while(pp < p.size() && p[pp] == '*')
            pp ++;
        return pp == p.size();
    }
};

运行结果：
解法2:动态规划
此题目动态规划解法类似于Regular Expression Matching
那么先来定义dp数组吧，我们使用一个二维 dp 数组，其中 dp[i][j] 表示 s中前i个字符组成的子串和p中前j个字符组成的子串是否能匹配。大小初始化为 (m+1) x (n+1)，加1的原因是要包含 dp[0][0] 的情况，因为若s和p都为空的话，也应该返回 true，所以也要初始化 dp[0][0] 为 true。还需要提前处理的一种情况是，当s为空，p为连续的星号时的情况。由于星号是可以代表空串的，所以只要s为空，那么连续的星号的位置都应该为 true，所以我们现将连续星号的位置都赋为 true。然后就是推导一般的状态转移方程了，如何更新 dp[i][j]，首先处理比较 tricky 的情况，若p中第j个字符是星号，由于星号可以匹配空串，所以如果p中的前 j-1 个字符跟s中前i个字符匹配成功了（ dp[i][j-1] 为true）的话，那么 dp[i][j] 也能为 true。或者若p中的前j个字符跟s中的前i-1个字符匹配成功了（ dp[i-1][j] 为true ）的话，那么 dp[i][j] 也能为 true（因为星号可以匹配任意字符串，再多加一个任意字符也没问题）。若p中的第j个字符不是星号，对于一般情况，我们假设已经知道了s中前 i-1 个字符和p中前 j-1 个字符的匹配情况（即 dp[i-1][j-1] ），那么现在只需要匹配s中的第i个字符跟p中的第j个字符，若二者相等（ s[i-1] == p[j-1] ），或者p中的第j个字符是问号（ p[j-1] == ‘?’ ），再与上 dp[i-1][j-1] 的值，就可以更新 dp[i][j] 了。
参见代码如下：

class Solution {
public:
    bool isMatch(string s, string p) {
        int m = s.size();
        int n = p.size();
        vector<vector<bool>>dp (m +1,vector<bool>(n+1, false));
        dp[0][0] = true;
        for(int i = 0; i < p.size(); i++)
        {
            if(p[i] == '*' && dp[0][i])
                dp[0][i+1] = true;
        }
        for(int i =0; i < m; i++)
        {
            for(int j =0; j < n; j++)
            {
                if(p[j] == '*')
                {
                    dp[i+1][j+1] = dp[i+1][j] || dp[i][j+1];
                    
                }else
                {
                    dp[i+1][j+1] = (s[i]==p[j] || p[j] =='?') && dp[i][j];
                }
            }
        }
        return dp[m][n];
    }
};

参考： https://leetcode.com/problems/wildcard-matching/discuss/17810/Linear-runtime-and-constant-space-solution https://www.cnblogs.com/grandyang/p/4401196.html https://www.youtube.com/watch?v=-8QnRMyHo_o </vector