A DP solution in C++.


  • -2
    X
    class Solution {
    public:
        bool isMatch(const char *s, const char *p) {
            if(s == NULL || p == NULL) return false;
            
            //for p and s both not end.
            while(*p != '\0' && *s != '\0'){
                
                //for *p represents any character.
                if(*p == '.' && *(p + 1) != '*'){
                    ++p;
                    ++s;
                }
                
                //for *p and *(p+1) is ".*", it can match one character or none(be skipped).
                else if(*p == '.') return (isMatch(s + 1, p) || isMatch(s, p + 2));
                
                //*p != '.' and *(p+1) == '*'
                else if(*(p + 1) == '*'){
                    if(*p != *s) return isMatch(s, p + 2);
                    else return (isMatch(s + 1, p) || isMatch(s, p + 2));
                }
                
                //*p is a normal character and not followed by '*'.
                else{
                    if(*p == *s){
                        ++p;
                        ++s;
                    }
                    else return false;
                }
            }
            
            //for p and s both end.
            if(*p == '\0' && *s == '\0') return true;
            
            //for p ends but s does not.
            if(*p == '\0') return false;
            
            //for s ends but p does not. Requires each character followed by a '*' until string p ends.
            while(*p != '\0' && *(p + 1) == '*')
                p += 2;
            if(*p == '\0') return true;
            return false;
        }
    };

Log in to reply
 

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