8-lines in C++...


  • 23

    To check for unique abbreviation, we maintain a mapping from a specific abbreviation to all words which have the abbreviation. Then we just need to check no other words have the same abbreviation as the given word.

    The code is as follows.

    class ValidWordAbbr {
    public:
    	ValidWordAbbr(vector<string> &dictionary) {
    		for (string& d : dictionary) {
    			int n = d.length();
    			string abbr = d[0] + to_string(n) + d[n - 1];
    			mp[abbr].insert(d);
    		}
    	}
    
    	bool isUnique(string word) {
    		int n = word.length();
    		string abbr = word[0] + to_string(n) + word[n - 1];
    		return mp[abbr].count(word) == mp[abbr].size(); 
    	}
    private:
    	unordered_map<string, unordered_set<string>> mp;
    };
     
     
    // Your ValidWordAbbr object will be instantiated and called as such:
    // ValidWordAbbr vwa(dictionary);
    // vwa.isUnique("hello");
    // vwa.isUnique("anotherWord");

  • 0
    R

    using hashmap<string,vector<string> > is enough....

    class ValidWordAbbr {
    public:
        unordered_map<string, vector<string>> um;
        ValidWordAbbr(vector<string> &ws) {
            um.clear();
            for(auto e: ws){
                string cur = e.size()>2 ? e[0]+to_string(e.size()-2)+e.back() : e;
                um[cur].push_back(e);
            }
        }
    
        bool isUnique(string ws) {
            string cur = ws.size()>2 ? ws[0]+to_string(ws.size()-2)+ws.back() : ws;
            return !um.count(cur) || um[cur].size()==1 && um[cur][0]==ws;
        }
    };
    
    
    
    
    // Your ValidWordAbbr object will be instantiated and called as such:
    // ValidWordAbbr vwa(dictionary);
    // vwa.isUnique("hello");
    // vwa.isUnique("anotherWord");
    
    
    class ValidWordAbbr {
    public:
        unordered_map<string, unordered_set<string>> um;
        ValidWordAbbr(vector<string> &dict) {
            for(auto e: dict){
                string cur = (e.size() > 2) ? (e[0]+to_string(e.size()-2)+e.back()) : e;
                um[cur].insert(e);
            }
        }
    
        bool isUnique(string e) {
            string cur = (e.size() > 2) ? (e[0]+to_string(e.size()-2)+e.back()) : e;
            return !um.count(cur) || um[cur].size()==1 && um[cur].count(e);
        }
    };
    
    
    // Your ValidWordAbbr object will be instantiated and called as such:
    // ValidWordAbbr vwa(dictionary);
    // vwa.isUnique("hello");
    // vwa.isUnique("anotherWord");

  • 0

    Enough? Well, using unordered_set is more efficient in both space and time.


  • 0
    R

    I mean hashset is not needed inside. But all of our solution is right


  • 2

    Well, for an interview question, correctness is just the least requirement and efficiency is very important: anything that can improve efficiency is worthwhile and thus needed.


  • 0
    W

    I am a little confused why you use map in the solution. Using only one unordered_set to store all the abbreviations in the dict and look up the abbreviation set for each word should be enough. Besides, in Jianchao's solution, if the length of a word is less than 2, it should no be transformed. The length in the abbreviation should be n-2 instead of n.


  • 0
    R

    using map, as if [hello], isunique(hello) should be true, as no other word except hello is h3o, just for processing this case. Yeah I also think that he did not process word len <=2 case


  • 0

    Well, for words of length not greater than 2, if I process them separately, the code will become longer. Why not unify them into the case of other words to make the code clean? Also, I do not store the real abbreviations, but this makes the code clean and also works. No one requires us to save the real abbreviations and this problem just requires us to check for unique abbreviations. This is the most clean way that I have found to solve it.


  • 0
    W

    When only using unordered_set to record the abbreviation of each word in the dictionary, for the case [hello], the unordered_set will be [h3o], isunique still returns true. I am still confused why we need map here. Could you please give me a little more explanations? Thanks.


  • 0
    W

    Sorry. I got the problem of using only unordered_set. Thanks.


  • 0
    Y

    can you tell me how do you handle ["a","a"] isUnique("a") return true case?


  • 0
    N

    for the input ["a"], isUnique(""), your string abbr = word[0] + to_string(n) + word[n - 1]; would cause undefined behavior, right?


  • 0
    S

    This returns true definitely, cuz they are all converted into "a1a".


  • 0
    J

    I don't think in this case, @ruichang unordered_set is more efficient than vector. Since he is just checking the size and compare the first element in the vector, still O(1) time, right? for unordered_set, to hash the string also takes time.


  • 0
    F

    @jianchao.li.fighter why there is an memory limited exceeded error when I directly run your code?


  • 0
    N

    Have you tried submitting it? It does not get acceptance! charming but no use!


  • 0
    H

    @JieGhost

    If you are only using vector , this line !um.count(cur) will give you O(n) time.


  • 0
    X

    Change unordered_set to set will make the code accept.


  • 0

    If you want the code to accept, you have to check that the string size is >2 before you place it in the form of e=str[0] + to_string(n) + str[n-1] (SHOWN BELOW)

            for(string& str:dictionary){
                int n= str.length();
                string e= n>2?str[0] + to_string(n) + str[n-1]:str;
                m1[e].insert(str);
            }
    

  • 0
    Z

    In isUnique function, is it necessary to check whether the key abbr exists before accessing mp[abbr]?
    It seems that mp.size() may grow when checking more and more words.


Log in to reply
 

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