C++ 62ms beats 100%


  • 0

    Solution 1

    Hash Table, 62ms, 100%.

    class WordDictionary {
    public:
        WordDictionary() {}
        
        void addWord(string word) {
            words[word.size()].push_back(word);
        }
        
        bool search(string word) {
            for(auto s: words[word.size()]) if(isEqual(s, word)) return true;
            return false;
        }
        
    private:
        unordered_map<int, vector<string>>words;
        
        bool isEqual(string a, string b){
            for(int i = 0; i < a.size(); i++){
                if(b[i] == '.') continue;
                if(a[i] != b[i]) return false;
            }
            return true;
        }
    };
    

    Solution 2

    Trie, 88ms.

    struct TrieNode{
        bool isKey;
        TrieNode* next[26];
        TrieNode():isKey(false){
            memset(next, NULL, sizeof(next));
        }
    };
    
    class WordDictionary {
    public:
        WordDictionary() {
            root = new TrieNode();
        }
        
        void addWord(string word) {
            TrieNode* node = root;
            for(auto c: word){
                if(!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
                node = node->next[c - 'a'];
            }
            node->isKey = true;
        }
        
        bool search(string word) {
            return helper(word, root);
        }
    
    private:
        TrieNode* root;
        
        bool helper(string word, TrieNode* node){
            for(int i = 0; i < word.size(); i++){
                char c = word[i];
                if(c != '.'){
                    if(!node->next[c - 'a']) return false;
                    node = node->next[c - 'a'];
                }
                else{
                    bool found = false;
                    int j = 0;
                    for(; j < 26; j++){
                        if(node->next[j]) found |= helper(word.substr(i + 1), node->next[j]);
                        if(found) return true;
                    }
                    if(j == 26) return false;
                }
            }
            return node->isKey;
        }
    };
    

Log in to reply
 

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