44. Wildcard Matching(Leetcode每日一题-2020.07.05）

本文主要是介绍44. Wildcard Matching(Leetcode每日一题-2020.07.05），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Problem

Given an input string (s) and a pattern §, 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 *.

Example1

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

Example2

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

Example3

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

Example4

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

Example5

Input:
s = “acdcb”
p = “a*c?b”
Output: false

Solution

与leetcode第10题类似
在这里插入图片描述

class Solution {
public:bool isMatch(string s, string p) {int m = s.length();int n = p.length();vector<vector<bool>> dp(m+1,vector<bool>(n+1,false));s = ' ' + s;p = ' ' + p;dp[0][0] = true; //两个都是空串,匹配for(int i = 0;i<=m;++i){for(int j = 1;j<=n;++j){if(p[j] == '*'){dp[i][j] = dp[i][j-1] || (i > 0 && dp[i-1][j]);}else{dp[i][j] = (s[i] == p[j] || p[j] == '?') && (i > 0 && dp[i-1][j-1]);}}}return dp[m][n];}
};