注意不要盲目相信以下内容! 不要盲目相信以下内容! 不要盲目相信以下内容! (重要的事情说三遍),虽然以下内容也经过了我的验证,但是我的验证可能有错误的地方,欢迎大家留言告知。希望这篇文章成为你深入探索相关领域的引子和启发,而不是标准答案。
‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s,const char *p)
Some examples:
isMatch(“aa”,”a”) → false
isMatch(“aa”,”aa”) → true
isMatch(“aaa”,”aa”) → false
isMatch(“aa”,“a*”) → true
isMatch(“aa”,“.*”) → true
isMatch(“ab”,“.*”) → true
isMatch(“aab”,“c*a*b”) → true
在Leetcode上看到了一种非常漂亮的递归解法,比我自己一堆判断的写法漂亮好多,转出来参考一下~
bool isMatch(string s,string p) {
if@H_502_42@ (p.empty@H_502_42@()) return@H_502_42@ s.empty@H_502_42@();
if@H_502_42@ ('*'@H_502_42@ == p[1@H_502_42@])
// x* matches empty string or at least one character: x* -> xx*@H_502_42@
// *s is to ensure s is non-empty@H_502_42@
return@H_502_42@ (isMatch(s,p.substr(2@H_502_42@)) || !s.empty@H_502_42@() && (s[0@H_502_42@] == p[0@H_502_42@] || '.'@H_502_42@ == p[0@H_502_42@]) && isMatch(s.substr(1@H_502_42@),p));
else@H_502_42@
return@H_502_42@ !s.empty@H_502_42@() && (s[0@H_502_42@] == p[0@H_502_42@] || '.'@H_502_42@ == p[0@H_502_42@]) && isMatch(s.substr(1@H_502_42@),p.substr(1@H_502_42@));
}