难度:Hard
原题连接
内容描述
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
思路 - 时间复杂度: O(n^2)- 空间复杂度: O(n^2)******
刚开始做的时候以为是一道大模拟题，但是做的时候才发现可以用DP。在使用DP时先找到状态转移方程。这里我们定义数组dp[i][j]表示第字符串 p 中第 i - 1个字母之前的字符串与字符串 s 中的第 j - 1个字母之前的子串匹配，我们就可以写出相应的状态转移方程当p[i] == '?'或者p[i] == s[j]时，dp[i + 1][j + 1] = dp[i][j],当p[i] == '*'时。j < p.length(),所有dp[i + 1][j + 1] = dp[i][j],并且dp[i + 1][j] = dp[i][j],最后返回dp[p.length()][s.length() - 1]
class Solution {
public:
bool isMatch(string s, string p) {
if(!p.length())
return !s.length();
s.push_back(' ');
int dp[p.length() + 1][s.length() + 1];
for(int i =0;i <= p.length();++i)
for(int j = 0;j <= s.length();++j)
dp[i][j] = 0;
int count1 = 1;
dp[0][0] = 1;
for(int i = 0;i < p.length();++i)
{
for(int j = 0;j < s.length();++j)
if(p[i] == '?' || p[i] == s[j])
dp[i + 1][j + 1] = dp[i][j];
else if(p[i] == '*' && dp[i][j])
{
dp[i + 1][j + 1] = 1;
dp[i + 1][j] = 1;
++j;
while(j < s.length())
{
dp[i + 1][j + 1] = 1;
++j;
}
}
}
return dp[p.length()][s.length() - 1];
}
};