本文共 3017 字，大约阅读时间需要 10 分钟。

class Solution {//1. No match. Simply return false. This is the last case in the program.//2. Single match. Either *s == *p, or *p == '?'. The return value of this case depends on the //result of the rest parts of both s and p (recursion call), which start at the 'diagonal' position by advancing both s and p by 1 (++s, ++p)//3. Star case, i.e. when *p == '*'. This is where the complication comes in. //A star can match 0, 1, 2, ..., to the end of string s. So, as long as one of the substrings match (recursion call), //after advance over '*', it returns true. This case returns false only after exhausting all possible substrings without a match.//update row by row, should practice more, DP, the time complexity is O(n*m)public:	bool isMatch(const char *s, const char *p) {		// Start typing your C/C++ solution below		// DO NOT write int main() function		if (!*s && !*p) return true;		int ms_max = 1;//size of *s		const char* ss = s;		while(*ss){ ++ms_max; ++ss;}		int np_max = 1;		const char* pp = p;		while(*pp){ if(*pp!='*') ++np_max; ++pp;}		if(ms_max < np_max) return false;		vector
   
    
      > r(2, vector
     
      (ms_max, false));//for the sake of saving space 		bool flag = 1;		r[0][0] = true;		do		{//*p			int ms = 1;			ss = s;			if (*p == '*')			{				while(*p == '*') ++p;//skip consecutive star				--p;				r[flag][0] = r[!flag][0];//from the previous row, because star can contain zero character				for( ;ms <= ms_max; ++ms)				{//up and left					if (r[!flag][ms] || r[flag][ms-1]) r[flag][ms] = true;					else r[flag][ms] = false;				}			}			else			{				do				{//for every character in p, update the row 					bool r_flag = false;					if (*ss == *p || *p == '?')						r_flag = r[!flag][ms-1];//diagonal					r[flag][ms]=r_flag;					++ms;++ss;				}while(*ss);//*s				r[flag][0] = false;//there must be some character in ss, if current character in p is not star			}			++p;			flag = !flag;//very fantastic		}while(*p);		return r[!flag][ms_max-1];	}};
     
    
   

second time

class Solution {//if strlen is used, then it will be TLE//iteration based solutionpublic:    bool isMatch(const char *s, const char *p) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        //int len1 = strlen(s);        //int len2 = strlen(p);                bool star = false;        const char* starPtr = NULL;        const char* savePtr = NULL;        while(*s != '\0')        {            if(*p == '?') s++, p++;            else if(*p == '*')            {                while(*p == '*') p++;                p--;                starPtr = p;                p++;                savePtr = s;                star = true;            }            else             {                if(*s == *p) s++, p++;                else                {                    if(star == true) s = ++savePtr, p = starPtr+1;//depend on star                    else return false;                }            }        }        while(*p == '*') p++;        return (*s == '\0' && *p == '\0');    }};

转载地址：http://ahxti.baihongyu.com/