First, we try to use recursive solution to solve this problem.
We face different condition of pattern character to use different strategy.
(1) ‘?’ :if the pointerS (index which use to pointer to the string) has larger than last one (point to ”) return false(which means that pattern needs one character to match while string has no character to match) . If not, return matchProcess(s,pointerS+1,p,pointerP+1);(return the result of next comparison,pointerS and pointerP points to their next one)
(2)’*’ : we try to represent the ‘*’ from empty string to all the string left, which means we will try the string left after ‘*”s represent, if they are match, then the string including ‘*’ is match. We will try one by one (‘*’ represent empty string to all the string left(after the pointerS)).If all the possibility have been tried, we can assert that string is not match(return false)
(3)check two character(pattern’s char is not ‘?’or ‘*’) .If not match,return false.If these two character are matched,return the result of pointer moving to next one.(pointerS+1,pointerP+1)
class Solution
{
private:
bool matchProcess(string s,int pointerS,string p,int pointerP)
{
if (pointerP==p.length())//如果pattern串已经扫描完了，就需要检查string串是否也扫描完了。如果string 串没有扫描完，意味着return false。
{
if (pointerS==s.length()) return true;//
else return false;
}
char chS=s[pointerS];
char chP=p[pointerP];
if (chP=='?')
{
if (pointerS==s.length()) return false;//如果pattern串要求一个single字符，但是string串已经扫描完了，意味着不匹配。
return matchProcess(s,pointerS+1,p,pointerP+1);//检查后面串的匹配情况，这个单一字符已经匹配了。
}
else if (chP=='*')
{
for (int i=pointerS; i<=s.length(); i++)//因为*可以匹配空串，所以从pointerS开始后数,因为可能整个string串都匹配这个*号，所以枚举的上限是s.length()就是string串已经遍历完了。
{
if (matchProcess(s,i,p,pointerP+1)) return true;//如果后面的可以匹配，返回true.
}
return false;//如果所有结果都遍历了还是没有合适的就返回false
}
else if (chS!=chP)
{
return false;
}
else return matchProcess(s,pointerS+1,p,pointerP+1);//匹配了单一字符，比如说string串的字符是a,pattern串的字符也是a,两者相等，指针往后挪一位再比较
}
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string dealString(s);
string dealPattern(p);
return matchProcess(dealString,0,dealPattern,0);
}
};
The recursive solution is easy to understand, it can pass the small data test, but fail in the large data test. After I searched on the Internet, I found a solution to it.
The main idea of this solution is to jump of the ‘*’, and compare the substring between them. For example, if the string is “dbabc” and the pattern is “*abc*”. We will jump off the first ‘*’ and compare the substring of pattern(“abc”) with the string of “dbabc”.If we find a dismatch(because the character will compare one by one) we can assume that ‘*’ represent more characters and try again.
Because the last one of the pattern is ”(Of course, it will not count on the matching.) and the last one of the string is also ”.If the pointer of string move to ”,it mean that we have a chance to find a match one, because if the string is not match the front part of the pattern (it will return false immediately.For example, find a mismatch characters, the pointer of string points to ‘b’ but the pointer of pattern points to ‘a’ and there are not ‘*’ happen before.) After the pointer of string points to ”(means equal to the length of string), we still need to check if the rest part of pattern are all ‘*’.If the rest part of the pattern are not all ‘*’, it means that empty string could not represent the rest part of pattern, it means that the string is not match.
(1) ‘?’ pointerS and pointerP moving to next.(Here,we do need to worry about whether the pointerP will point to some place after ”,because pointerP only add 1 if the character pointerS point to is equal to pointerP point to or pointerP points to ‘?’.Both of possibility will not happen. Because the ending condition of loop is pointerS points to ”.)
(2) ‘*’ mark down the pointerS.(It is the first one that could match the substring after’*’ in the pattern.) mark down the place which just after ‘*'(It may have a few ‘*’ occur,thus we need to jump off all the ‘*’.)PointerP equals this one (This one is the one need to compare.) If pointerP equals the last one, it can just return true(all the character left can use ‘*’ to represent.)
(3) find a mismatch(not ‘*’ or ‘?’), we can check if there is ‘*’ before.If there is a ‘*’ before, we could move pointerS to the next one of the place mark down.(means that ‘*’ represent a more bit.)PointerP move to the mark down one.(The character in pattern need to be check.(after the last ‘*’)).If there is not a ‘*’ happen before, just return false(A mismatch.)
(4) match, pointerS++,pointerP++
After the loop, we need to check the left part of the pattern. If there are not all ‘*’, it means that empty string in string can not represent the left part of pattern.
class Solution {
public:
bool isMatch(const char *s, const char *p) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
string dealString(s);//转成字符串，方便处理
string dealPattern(p);
bool hasStar=false;//判断之前有没有星号的
int pointerS=0;//指向string的指针
int pointerP=0;//指向pattern的指针
int lastStarComparePointerS;//记录string匹配星号之后的第一个字符的指针
int lastStarComparePointerP;//记录pattern上后面第一个非星号的字符的指针
while (pointerS<dealString.length())//pointerS小于string的长度
{
char chS=dealString[pointerS];//拿指向对应的字符，注意这里可以拿到全0（字符串结束符号）
char chP=dealPattern[pointerP];
if (chP=='?')
{//如果遇到？任意字符都可以，相当于字符相等一样，两个指针都加1
pointerS++;
pointerP++;
continue;
}
else if (chP=='*')
{
hasStar=true;//如果遇到*，把这个记录前面是否包含一个*号的变量置为true
lastStarComparePointerS=pointerS;//记录匹配了*之后的第一个字符的index，这里由于*可以代表空串，所以直接就是当前指向的string的index
lastStarComparePointerP=pointerP;
while (dealPattern[lastStarComparePointerP]=='*')
{
lastStarComparePointerP++;
}//记录*后面第一个非*号的字符的index（有可能有连续几个*）
if (lastStarComparePointerP==dealPattern.length()) return true;
pointerP=lastStarComparePointerP;//把pattern的pointer挪到*后面的第一个非*的字符
}
else if (chS!=chP)
{//如果字符不相等
if (!hasStar) return false;//查看前面是否有*号，如果没有*号，返回false
//如果有星号，则把记录之前一个星号后面的起始匹配的位置往后挪
lastStarComparePointerS++;
pointerS=lastStarComparePointerS;
pointerP=lastStarComparePointerP;//跳到之前一个*后面的一个非星号的字符
}
else
{
pointerS++;
pointerP++;
}
}
//有可能string串先被扫完，这时候必须检查pattern串剩下的是否为*,如果不是，证明pattern后面多出来的东西没有办法被空串匹配,需要返回false
while (dealPattern[pointerP]=='*' )
{
pointerP++;
}
if (pointerP==dealPattern.length()) return true;
else return false;
}
};
Poly-Thinking 