3ms C solution using O(mn) time and O(n) space


  • 0
    H
    bool isMatch(char *s, char *p){
        int i;
        
        int ls = strlen(s);
        int lp = strlen(p);
        bool* m = malloc((ls + 1) * sizeof(bool));
        
        // init
        m[0] = true;
        for (i = 1; i <= ls; i++) {
            m[i] = false;
        }
        
        int ip;
        for (ip = 0; ip < lp; ip++) {
            if (ip + 1 < lp && p[ip + 1] == '*') {
                // do nothing
            }
            else if (p[ip] == '*') {
                char c = p[ip - 1];
                for (i = 1; i <= ls; i++) {
                    m[i] = m[i] || (m[i - 1] && (s[i - 1] == c || c == '.'));
                }
            }
            else {
                char c = p[ip];
                for (i = ls; i > 0; i--) {
                    m[i] = m[i - 1] && (s[i - 1] == c || c == '.');
                }
                m[0] = false;
            }
        }
        
        bool ret = m[ls];
        free(m);
        return ret;
    }

  • 0
    Q

    cool code, but what if the first character of p is *?


  • 0
    H

    right, it will cause illegal memory read. but that is not a valid input, i guess.


Log in to reply
 

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