C++ unordered_map & set solution with explanation.


  • 0
    M
    class ValidWordAbbr {
    public:
        ValidWordAbbr(vector<string> &dictionary) {
            for (int i = 0; i < dictionary.size(); ++i)
            {
                string currentString = dictionary[i];
                if (currentString.length() == 0)
                {
                    continue;
                }
                
                string temp = currentString.substr(0, 1) + currentString.substr(currentString.length() - 1, 1);
                m[currentString.length()][temp].insert(currentString);
            }
        }
    
        bool isUnique(string word) {
            if (m.empty())
            {
                return true;
            }
            
            auto temp = m.find(word.length());
            if (temp == m.end())
            {
                // No words in the dict has the same length as input word. Unique!
                return true;
            }
            
            auto temp2 = temp->second.find(word.substr(0, 1) + word.substr(word.length() - 1, 1));
            
            if (temp2 == temp->second.end())
            {
                // No words in the dict has the same head and tail char as input word. Unique!
                return true;
            }
            
            if (temp2->second.find(word) != temp2->second.end() && temp2->second.size() == 1)
            {
                // The only word in dict has the same abbr as the input word, and they are the same words! Unique!
                return true;
            }
            
            // Well, there're other words in the dict has the same abbr as input word.
            return false;
        }
        
    private:
        unordered_map <int, unordered_map<string, set<string>>> m;
    };
    
    
    // Your ValidWordAbbr object will be instantiated and called as such:
    // ValidWordAbbr vwa(dictionary);
    // vwa.isUnique("hello");
    // vwa.isUnique("anotherWord");
    

Log in to reply
 

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