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

思路：基本和leetcode10 正则表达式匹配思路一致。

方法一：记忆化搜索

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         int lens = s.length(), lenp = p.length();
 5         vector<vector<int> > memo(lens + 1, vector<int>(lenp + 1, -1));
 6         return isMatch(s, p, 0, 0, memo);
 7     }
 8     bool isMatch(string s, string p, int i, int j, vector<vector<int> > &memo) {
 9         if (memo[i][j] != -1) {
10             return memo[i][j];
11         }
12         int ans;
13         if (j >= p.length()) {
14             ans = (i == s.length());
15         } else {
16             bool first_match = (i < s.length() && (s[i] == p[j] || p[j] == '?' || p[j] == '*'));
17             if (p[j] == '*') {
18                 ans = isMatch(s, p, i, j + 1, memo) || (first_match && isMatch(s, p, i + 1, j, memo));
19             } else {
20                 ans = first_match && isMatch(s, p, i + 1, j + 1, memo);
21             }
22         }
23         memo[i][j] = ans;
24         return ans;
25     }
26 };

方法二：动态规划

 1 class Solution {
 2 public:
 3     bool isMatch(string s, string p) {
 4         int lens = s.length(), lenp = p.length();
 5         bool dp[lens + 1][lenp + 1];
 6         memset(dp, false, sizeof(dp));
 7         //vector<vector<bool> > dp(lens + 1, vector<bool>(lenp + 1, false)); //用vector耗时
 8         dp[0][0] = true;
 9         for(int i = 1; i <= lenp; i ++) {
10             dp[0][i] = p[i - 1] == '*' && dp[0][i - 1];
11         }
12         for(int i = 1; i <= lens; i ++) {
13             for(int j = 1; j <= lenp; j ++) {
14                 if(p[j - 1] != '*') {
15                     if ((s[i - 1] == p[j - 1]) || (p[j - 1] == '?')) {
16                         dp[i][j] = dp[i - 1][j - 1];
17                     }
18                 } else {
19                     dp[i][j] = (dp[i][j - 1] || dp[i - 1][j]); //如果长度为j的p，最后一个是'*',可以将'*'变成s的最后一个字符，则有dp[i][j] = dp[i - 1][j], 或者'*'变为空。dp[i][j] = dp[i][j - 1]
20                 }
21             }
22         }
23         return dp[lens][lenp];
24     }
25 };