Can anyone share a solution using C?


  • 0
    C

    Using Python and cache to solve this problem is not that hard, but I was wondering how to solve it using C. Can anybody share his or her C solution?


  • 0
    C

    OK, I came up with one. C solution 4ms beats 100% (some intermediate memory not freed...)

    typedef struct {
        char* s;
        char** res;
        int size;
    } cache_item;
    
    cache_item cache[1024];
    int wptr, wdsize;
    char** wd;
    
    void cache_store(char* s, char** res, int size)
    {
        cache_item* c = &cache[wptr++];
        c->s = s;
        c->res = res;
        c->size = size;
    }
    
    cache_item* find_cache(char* s)
    {
        int i;
        for (i = 0; i < wptr; i++) {
            if (cache[i].s == s)
                return &cache[i];
        }
        return NULL;
    }
    
    // if true, return sub len, else return 0
    int startswith(char* s, char* sub)
    {
        int i = 0;
        while (sub[i] && sub[i] == s[i]) i++;
        return sub[i] ? 0 : i;
    }
    
    char** wordBreak2(char* s, int* returnSize) {
        cache_item* c = find_cache(s);
        if (c) {
            *returnSize = c->size;
            return c->res;
        }
        char** res = malloc(1024 * sizeof(char*));
        int i, j, pos, size2, rptr = 0;
        char **res2, *tmp;
    
        for (i = 0; i < wdsize; i++)
        {
            if (pos = startswith(s, wd[i]))
            {
                if (pos == strlen(s))
                {
                    tmp = res[rptr++] = malloc(1024);
                    strcpy(tmp, s);
                    continue;
                }
                res2 = wordBreak2(s + pos, &size2);
                for (j = 0; j < size2; j++) {
                    tmp = res[rptr++] = malloc(1024);
                    memcpy(tmp, s, pos); tmp[pos] = ' '; strcpy(tmp+pos+1, res2[j]);
                }
            }
        }
        cache_store(s, res, rptr);
        *returnSize = rptr;
        return res;
    }
    
    char** wordBreak(char* s, char** wordDict, int wordDictSize, int* returnSize) {
        wptr = 0;
        wdsize = wordDictSize;
        wd = wordDict;
        return wordBreak2(s, returnSize);
    }
    

  • 0
    C

    It is just a C version of my Python code

    class Solution(object):
        def wb2(self, s):
            if s in self.d: return self.d[s]
            res = []
            for w in self.wordDict:
                if s.startswith(w):
                    if w == s: 
                        res.append(s)
                        continue
                    r1 = self.wb2(s[len(w):])
                    res += [w + " " + item for item in r1]
            self.d[s] = res
            return res
        
        def wordBreak(self, s, wordDict):
            """
            :type s: str
            :type wordDict: Set[str]
            :rtype: List[str]
            """
            self.d = {}
            self.wordDict = wordDict
            return self.wb2(s)
    

Log in to reply
 

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