An intuitive solution may not work out here, using Trie here accepted as best submission in C, well-explained


  • 1

    If we try to use the intuitive solution to traverse the whole string array to search, the TLE problem will certainly come around; so here we are to take advantage of a new structure Trie which is often used to accelerate the searching process apart from hash and binary search in ordered array.

    After getting close to this structure, I assume that you have already know the key to hack it. Needless for further explanation now.

    Bang! End of story!

    • Space cost O(n)
    • Time cost O(kn) -> k should be the length of the word, even all character is dot the worst time complexity will also be limited under 26kn; so that's it.

    #define SIZE 26
    struct WordDictionary
    {
        bool isWord; //determine whether a word exists in the path;
        struct WordDictionary **children;
    };
    
    struct WordDictionary* nodeMaker()
    {
        struct WordDictionary *t = (struct WordDictionary*)malloc(sizeof(struct WordDictionary));
        t->isWord = false;
        int space = sizeof(struct WordDictionary*)*SIZE;
        t->children = (struct WordDictionary**)malloc(space);
        memset(t->children, 0, space);
        return t;
    }
    struct WordDictionary* wordDictionaryCreate()
    {
        return nodeMaker();
    }
    
    void addWord(struct WordDictionary* dict, char* word)
    {
        struct WordDictionary *cur = dict;
        for(int i = 0; word[i]; i++)
        {
            if(!(cur->children[word[i]-'a']))
                cur->children[word[i]-'a'] = nodeMaker();
            cur = cur->children[word[i]-'a'];
        }
        cur->isWord = true; //set the flag for the existence of the word in the current path;
    }
    
    bool search(struct WordDictionary* root, char* word)
    {
        struct WordDictionary *cur = root;
        for(int i = 0; word[i]; i++)
        {
            if(!cur) return false; //the path is interrupted;
            if(word[i]!='.') //track the path down;
                cur = cur->children[word[i]-'a'];
            else if(word[i]=='.') //while there is dot, the possible paths can be all;
            {
                for(int j = 0; j < SIZE; j++) //try every possible path;
                    if(search(cur->children[j], word+i+1))
                        return true;
                return false; //all possible paths have failed;
            }
        }
        return cur&&cur->isWord; //the last checking;
    }
    
    
    void wordDictionaryFree(struct WordDictionary *dict)
    {
        free(dict->children);
        free(dict);
    }
    

Log in to reply
 

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