26*26 Index Table and HashTable Solution (C++)


  • 0
    X
    class ValidWordAbbr {
        vector<vector<unordered_map<int,string>>> table;
    public:
        ValidWordAbbr(vector<string> &dictionary) {
            table.clear();
            // Use first and last letter as index table, each cell is a hash table mapping length to string
            table= vector<vector<unordered_map<int,string>>>(26, vector<unordered_map<int, string>> (26));
            int wordSize;
            unordered_map<int, string> * map; //Pointer to this kind of hash table
            for(int i = 0; i < dictionary.size(); i++){
                wordSize = dictionary[i].size();
                map = &table[dictionary[i][0] - 'a'][dictionary[i][wordSize - 1] - 'a'];
                if(wordSize >= 2){ // Only analysis words of more than 1 letter
                    string sub = dictionary[i].substr(1, wordSize - 2);
                    if((*map).count(wordSize - 2) == 0) // Store the string in middle of the word
                        (*map)[wordSize - 2] = (sub);
                    else // More than 2 abbrs in Dictionary, use + to indicate
                        (*map)[wordSize - 2] = "+";
                };
            }
        }
    
        bool isUnique(string word) {
            int size = word.size();
            if(size == 1) return true; // Return TRUE for single letter words
            string sub = word.substr(1, size - 2);
            if(table[word[0] - 'a'][word[size - 1] - 'a'].count(size - 2) == 0) 
                return true; // No words in Dict match the abbr
            if(table[word[0] - 'a'][word[size - 1] - 'a'][size - 2] == "+")
                return false; // More than 1 words in Dict match the abbr
            return !table[word[0] - 'a'][word[size - 1] - 'a'][size - 2].compare(sub); // return TRUE if the string matches
        }
    };

  • 0
    Y

    you made a simple question complex.


Log in to reply
 

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