LeetCode第44題Wildcard Matching
4506 ワード
思想は主にここを参考にするが、そこにはchar*で保存された文字列があり、この文字列は最後に'0'文字で終わるため、上記のコードではp文字列は境界を越えない.現在、文字列はstringで保存されており、p文字列の下付き文字が境界を越えているかどうかを議論する必要があります.C++コード:
#include
#include
#include
using namespace std;
class Solution {
public:
bool isMatch(string s, string p) {
//ps s
int ps = 0;
//pp p
int pp = 0;
//ss , , ps ++ss
int ss = -1;
//p_start , , pp p_start+1
int p_start = -1;
while (ps < s.size())
{
if ( pp < p.size())
{
if (s[ps] == p[pp] || '?' == p[pp])
{
++ps;
++pp;
}
else if ('*' == p[pp])
{
p_start = pp++;
ss = ps;
}
else
{
// '*'
if (p_start >= 0)
{
ps = ++ss;
pp = p_start+1;
}
else
{
return false;
}
}
}
// p , s
else if (pp == p.size() && ps < s.size())
{
// '*'( p_start >= 0), ‘*’ , pp ps
if (p_start >= 0)
{
ps = ++ss;
pp = p_start+1;
}
else
{
return false;
}
}
//p s
else
{
return true;
}
}//while
// s p
for (;pp < p.size();++pp)
{
if ('*' != p[pp])
{
return false;
}
}
return true;
}
};
int main()
{
Solution s;
cout<"abbb", "a*b")<return 0;
}