# Help me! Exhausted. Need a more well-formed solution.

• Ahhhhhhhhhhhhh!
The following is my first solution which got TLE for long input.

``````// TLE Solution
class Solution {
private:
bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
public:
bool isMatch(const char *s, const char *p) {
if(!s || !p) return !s && !p;
// match single char
while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
if(!*p) return !*s;
if(*p != '*') return false;
// match '*'
while(*p == '*') ++p;
if(!*p) return true;
while(*s){
if(sameChar(*s, *p) && isMatch(s, p)) return true; // This line is inefficient!
++s;
}
return false;
}
};
``````

The line followed with a comment is the cause of TLE. In the light of @greed's solution, I added some lines in the `while` loop.

``````// AC Solution. I felt it's a little bit redundant, but I failed to simplify it.
class Solution {
private:
bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
public:
bool isMatch(const char *s, const char *p) {
if(!s || !p) return !s && !p;
// match single char
while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
if(!*p) return !*s;
if(*p != '*') return false;
// match '*'
while(*p == '*') ++p;
if(!*p) return true;
while(*s){
const char *ts = s, *tp = p;
while(*ts && *tp && sameChar(*ts, *tp)){ ++ts; ++tp; }
if(!*tp && !*ts) return true;
if(*tp == '*') return isMatch(ts, tp);
if(!*ts) return false; // This line is very very important!
// If s doesn't have enough char to match p, return false directly!
++s;
}
return false;
}
};
``````

The line `if(!*ts) return false;` plays a vital role to stop immediately for impossible case . But I'm not satisfied. I feel that the lines in the `while` loop are very similar to the three lines that match single chars. Seemingly it's repeating itself. I sat in front of my computer for two hours trying to simplify the code, but in the end I can only persuade myself it's irreducible. The following lines are my final submission. Can anyone give me a more elegant solution?

``````// AC Solution. I can only extract a function `guessStartlet` out of `isMatch`.
class Solution {
private:
bool sameChar(char s, char p){ return p == '?' ? true : s == p; }
void skipSameChar(const char *&s, const char *&p){
while(*s && *p && sameChar(*s, *p)){ ++s; ++p; }
}
bool guessStarlet(const char *s, const char *p){
while(*p == '*') ++p; // need only one '*'
if(!*p) return true; // p ends with '*'
while(*s){
const char *ts = s, *tp = p;
skipSameChar(ts, tp);
if(!*tp && !*ts) return true;
if(*tp == '*') return guessStarlet(ts, tp);
if(!*ts) return false;
++s;
}
return false;
}
public:
bool isMatch(const char *s, const char *p) {
if(!s || !p) return !s && !p;
// match single char
skipSameChar(s, p);
if(!*p) return !*s;
if(*p != '*') return false;
// match '*'
return guessStarlet(s, p);
}
};``````

• Share my DP solution:

``````class Solution {
public:
bool isMatch(const char *s, const char *p) {
if( !s || !p ) return !s && !p;
int N = strlen(s), M = strlen(p);

vector<int> lenl(M+1),lenr(M+1);
lenr[M] = lenl[0] = 0;
for(int j=M-1;j>=0;j--) lenr[j] = lenr[j+1] + (p[j]=='*'?0:1);
for(int j=1;j<=M;j++) lenl[j] = lenl[j-1] + (p[j-1]=='*'?0:1);

unordered_set<int> F{0}, G;
for(int i=0;i<=N;i++) G.insert(i);

for(int j=1;j<=M;j++) {
unordered_set<int> nF,nG;
for(int i=lenl[j];i<=N-lenr[j];i++) {
if( i > 0 && (p[j-1] == '?' || s[i-1]==p[j-1]) && F.count(i-1) )
nF.insert(i);
if( p[j-1] == '*' && G.count(i))
nF.insert(i);
if( nG.count(i-1) || nF.count(i) )
nG.insert(i);
}
F = nF;
G = nG;
}
return F.count(N);
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.