44. Wildcard Matching
难度:Hard
刷题内容
原题连接
- https://leetcode.com/problems/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
˼· **- ʱ�临�Ӷ�: 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];
}
};
