作者推荐
视频算法专题
本文涉及知识点
动态规划汇总
LeetCode44 通配符匹配
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
参数范围：
0 <= s.length, p.length <= 2000
s 仅由小写英文字母组成
p 仅由小写英文字母、‘?’ 或 ‘*’ 组成
动态规划
共有mn种状态，故空间复杂度是O(nm)，每种状态的转移时间复杂度是O(1)，故时间复杂度是O(nm)。m和n是p和s的长度。
| 动态规划的状态表示 | dp[i][j]等于p[0,i)和s[0,j)是否匹配 |
| 动态规划的转移方程 | 下文详细列出 |
| 动态规划的初始状态 | 除dp[0][0]=true外，全部false |
| 动态规划的填表顺序 | 一，如果p[0,j)全部是*，则dp[j][0]=true。二， i,j全部从小到大。由短到长处理子字符串,确保动态规划的无后效性 |
| 动态规划的返回值 | dp[m][n] |
转移方程
p[i-1]为*: a,不匹配任字符。b,匹配1到多个字符。匹配2个字符和匹配1个字符完全相同。
为? : 和dp[i-1][j-1]相同。
其它字符： p[i-1]==s[j-1] 且 dp[i-1][j-1]
代码
核心代码
class Solution {
public:
bool isMatch(string s, string p) {
const int m = p.length();
const int n = s.length();
vector<vector<bool>> dp(m + 1, vector<bool>(n + 1));
dp[0][0] = true;
for (int i = 0; (i < m)&&('*'==p[i]); i++)
{
dp[i + 1][0] = true;//p前面的*不匹配任何字符
}
for (int i = 1; i <= m; i++)
{
const char& ch = p[i - 1];
for (int j = 1; j <= n; j++)
{
if ('*' == ch)
{
const bool b1 = dp[i - 1][j];//*不匹配任何字符
const bool b2 = dp[i][j - 1];//*匹配字符1到x个字符
dp[i][j] = b1 || b2;
}
else if ('?' == ch)
{
dp[i][j] = dp[i - 1][j - 1];
}
else
{
dp[i][j] = dp[i - 1][j - 1]&&(ch == s[j-1]);
}
}
}
return dp.back().back();
}
};
测试用例
template<class T>
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s,p;
{
Solution sln;
s = "ab", p = "?*";
auto res = sln.isMatch(s, p);
Assert(true, res);
}
{
Solution sln;
s = "aa", p = "a";
auto res = sln.isMatch(s, p);
Assert(false, res);
}
{
Solution sln;
s = "aa", p = "*";
auto res = sln.isMatch(s, p);
Assert(true, res);
}
{
Solution sln;
s = "cb", p = "?a";
auto res = sln.isMatch(s, p);
Assert(false, res);
}
}
2022 年12月
class Solution {
public:
bool isMatch(string s, string p) {
unordered_set preDp;
preDp.insert(0);
for (const auto& ch : p )
{
unordered_set dp;
if (‘*’ == ch)
{
int iMin = *std::min_element(preDp.begin(), preDp.end());
for (; iMin <= s.length(); iMin++)
{
dp.insert(iMin);
}
}
else
{
for (const auto& pre : preDp)
{
if (pre < s.length())
{
if ((‘?’ == ch) || (ch == s[pre]))
{
dp.insert(pre + 1);
}
}
}
}
preDp.swap(dp);
if (preDp.empty())
{
return false;
}
}
return *std::max_element(preDp.begin(),preDp.end()) >= s.length();
}
};
23年8月
class Solution {
public:
bool isMatch(string s, string p) {
if (p.empty())
{
return s.empty();
}
vector vp;
int left = 0;
for (int i = 0; i < p.length()😉
{
while ((i < p.length()) && (‘’ != p[i]))
{
i++;
}
//p[i]为’\0’或
vp.emplace_back(p.substr(left, i - left));
while ((i < p.length()) && (’’ == p[i]))
{
i++;
}
left = i;
}
if ('’ == p.back())
{
vp.emplace_back(“”);
}
if (1 == vp.size())
{
return (s.length()p.length())&& (0Cmp(s,p));
}
const int iFirstLen = vp.front().length();
if (s.length() < iFirstLen)
{
return false;
}
if (0 != Cmp( s, vp.front()))
{
return false;
}
s = s.substr(iFirstLen);
vp.erase(vp.begin(), vp.begin()+1);
const int iRemain = s.length() - vp.back().length();
if (iRemain < 0)
{
return false;
}
if (0 != Cmp(s.substr(iRemain), vp.back()))
{
return false;
}
s = s.substr(0, iRemain);
vp.pop_back();
for (const auto& subP : vp)
{
const int ind = Cmp(s, subP);
if (-1 == ind)
{
return false;
}
s = s.substr(ind + subP.length());
}
return true;
}
int Cmp( const string& s , const string& strP)
{
int len = strP.length();
for (int i = 0; i+len <= s.length(); i++)
{
if (CmpInner(s, i, strP))
{
return i;
}
}
return -1;
}
bool CmpInner(const string& s,int si, const string& strP)
{
int len = strP.length();
for (int i = 0; i < len; i++)
{
if ((s[i+si] != strP[i]) && (‘?’ != strP[i]))
{
return false;
}
}
return true;
}
};
