题目
给你一个输入字符串 (s) 和一个字符模式 § ，请你实现一个支持 ‘?’ 和 ‘’ 匹配规则的通配符匹配：
‘?’ 可以匹配任何单个字符。
'’ 可以匹配任意字符序列（包括空字符序列）。
判定匹配成功的充要条件是：字符模式必须能够 完全匹配 输入字符串（而不是部分匹配）。
示例 1：
输入：s = “aa”, p = “a”
输出：false
解释：“a” 无法匹配 “aa” 整个字符串。
示例 2：
输入：s = “aa”, p = ""
输出：true
解释：'’ 可以匹配任意字符串。
示例 3：
输入：s = “cb”, p = “?a”
输出：false
解释：‘?’ 可以匹配 ‘c’, 但第二个 ‘a’ 无法匹配 ‘b’。
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(); }
};
2023年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; }
};
其它
视频课程
如果你觉得复杂，想从简单的算法开始，可以学习我的视频课程。
https://edu.csdn.net/course/detail/38771
我的其它课程
https://edu.csdn.net/lecturer/6176
测试环境
win7 VS2019 C++17
相关下载
doc版文档，排版好
https://download.csdn.net/download/he_zhidan/88348653
