Brief 6ms C code


  • 2
    W
    bool isMatch(char* s, char* p) {
        char *p0 = NULL, *s0 = NULL;
        while (*s) {
            if (*p == *s || *p == '?') {
                p++; 
                s++;
            }else if (*p == '*') { // save
                p0 = ++p;
                s0 = s;
            }else if (p0 != NULL) { // load
                p = p0;
                s = ++s0;
            }else {
                return false;
            }
        }
        while (*p == '*') p++;
        return !*s && !*p;
    }
    

  • 0
    D

    Wow! I really like this solution.

    I have a solution which is logically sound, and performs decent but extremely convoluted. Let me know if anyone has any tips on how to optimize the code with this solution as a starting point:

    #include <stdio.h>
    #include <string.h>
    #include <stdbool.h>
    
    bool isMatch(char* s, char* p);
    
    int main(int argc, char *argv[]) {
            printf("%d\n", isMatch(argv[1],argv[2]));
            return 0;
    }
    
    /*
     * finds index of pSub which doesn't contain '*' occuring in s,
     * s is null terminated where as pSub has length specified
     */
    int findPSub(char *pSub, int pSubLen, char *s) {
            char *sOrig = s;
            while(true) {
                    bool matched = true;
                    for(int i=0; i<pSubLen; i++) {
                            if(!s[i])
                                    return -1;
                            if(pSub[i]!='?' && pSub[i]!=s[i]) {
                                    matched = false;
                                    break;
                            }
                    }
                    if (matched)
                            return s-sOrig;
                    s++;
            }
    }
    
    /*
     * return true if pSub which does not contain '*'
     * matches the end of s
     */
    bool matchEnd(char *pSub, int pSubLen, char *s) {
            int sLen = strlen(s);
            if(sLen < pSubLen)
                    return false;
            for(int i=0; i<pSubLen; i++) {
                    if(pSub[i]!='?' && pSub[i]!=s[sLen-pSubLen+i])
                            return false;
            }
            return true;
    }
    
    bool isMatch(char* s, char* p) {
    /*
     * match the portion of p before the first occurance of '*'
     */
            while((*s && *p=='?') || (*p && *p==*s)) {
                    p++;
                    s++;
            }
            if (*p && *p!='*')
                    return false;
    
    /*
     * at this point p is a string of this form:
     * *p_1*p_2*...*p_n
     * each '*' can be any number of consecutive '*'
     * p_n can be empty string
     */
            char *pSub;
            int pSubLen;
    
    /*
     * this while loop once entered will always
     * execute a return statement inside
     */
            while(*p != '\0') {
    /*
     * at this point p is a string of this form:
     * *p_1*p_2*...*p_n
     * each '*' can be any number of consecutive '*'
     * p_n can be empty string
     *
     * each iteration of the loop iterates over a *p_i
     */
                    while(*p=='*')
                            p++;
                    pSub = p;
                    pSubLen = 0;
                    while(*p!='\0' && *p!='*') {
                            pSubLen++;
                            p++;
                    }
                    if (!*p)
                            return matchEnd(pSub, pSubLen, s);
    
                    int idx = findPSub(pSub, pSubLen, s);
                    if (idx < 0)
                            return false;
                    s += (idx+pSubLen);
            }
    
            return !*s;
    }
    

Log in to reply
 

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