[C++] Sharing my 7 line recursive solution (100ms) and 20 line DP solution (30ms).


  • 10
    S

    I'm sharing my recursive and DP solutions in C++. I'm a big recursion person so I first thought about the recursive solution first. Depending on the condition, you either advance one char in s or freeze s and advance two pointers in t. The only tricky part is in the base case. I basically loop and delete possible sequences of "X*" occurrences in t.

    Could somebody share some insights to make the code more elegant and efficient? One thing that comes to my mind is to somehow get rid of the strlen() function call.

    For the recursive formulation, it takes about 100ms.

    class Solution {
    public:
        bool isMatch(const char *s, const char *t) {
            if (*s=='\0') {
                while (strlen(t)>=2 && t[1]=='*') {t += 2;}
                return *t=='\0';
            }
    
            // if next char in t is not a star,
            if (t[1]!='*'){
                return s[0]==t[0]||t[0]=='.' ? isMatch(s+1,t+1) : false;
            // if next char in t is *, either skip this X* in t, or match X* to one char in s.
            } else {
                return strlen(t)>2&&isMatch(s,t+2) ? true : (s[0]==t[0]||t[0]=='.' ? isMatch(s+1,t) : false);
            }
        }
    };
    

    As for DP, it's straightforward if you understand the recursive relations. It takes 32ms.

    class Solution {
    public:
        bool isMatch(const char *s, const char *t) {
    
            vector<vector<bool>> V(strlen(s)+1, vector<bool>(strlen(t)+1,false));
            V[strlen(s)][strlen(t)] = true;
            
            // init bottom
            for (int i=0; i<(int)strlen(s)-1; i++) V[i][strlen(t)]=false;
            
            // init right
            for (int j=(int)strlen(t)-1; j>=0;j--){
                if (t[j]=='\0') V[strlen(s)][j]=true;
                
                if (t[j+1]=='*') V[strlen(s)][j]=V[strlen(s)][j+2];
            }
            
            // fill in dp from bottom right
            for (int j=(int)strlen(t)-1; j>=0; j--){
                if (t[j]=='*') continue;
                for (int i=(int)strlen(s)-1; i>=0; i--){
                    if (t[j+1]!='*')
                        V[i][j] = (s[i]==t[j]||t[j]=='.') ? V[i+1][j+1] : false;
                    else if (V[i][j+2]){
                        V[i][j] = true;
                    } else {
                        V[i][j] = (s[i]==t[j]||t[j]=='.') ? V[i+1][j] : false;
                    }
                }
            }
            return V[0][0];
        }
    };

  • 1
    R

    what's the time complexity of recursive solution


  • 0
    M

    Why do you initialize the bottom to false? Isn't it already false - per the initialization above it?


  • 0
    K

    You can get rid of strlens in recursive code rather easily/clumsily, depending on your taste: you don't need to know actual length, just whether it's 2 or more or less. Thus, using strnlen(t,2) and strnlen(t,3) in first and second cases, respectively, makes checks O(1) rather than O(len(s))


Log in to reply
 

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