288. Unique Word Abbreviation

问题来自 288. Unique Word Abbreviation

---

这道题我们可以先把dictionary里面的word都abbreviate，放到hash表里面。key是abbreviate得到的string，value是一个vector，因为不同的word得到的abbreviation有可能是一样的。然后check的时候只要找到对应的key即可。

---

1, 哈希

class ValidWordAbbr {
public:
    ValidWordAbbr(vector<string> &dictionary) {
        int size = dictionary.size();
        for(int i = 0; i < size; ++i)
        {
            string s = dictionary[i];
            int length = s.size();
            if(length <= 2)
                store[s].push_back(s);
            else
            {
                stringstream ss;
                ss << s[0] << length-2 << s[length-1];
                store[ss.str()].push_back(s);
            }
        }
    }

    bool isUnique(string word) {
        int length = word.size();
        string key;
        if(length <= 2)
            key = word;
        else
        {
            stringstream ss;
            ss << word[0] << length-2 << word[length-1];
            key = ss.str();
        }
        unordered_map<string, vector<string> >::iterator ite;
        if((ite=store.find(key)) == store.end()) return true;
        for(int i = 0; i < ite->second.size(); ++i)
            if(ite->second[i] != word) 
                return false;
        return true;
    }
private:
    unordered_map<string, vector<string> > store;
};


// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa(dictionary);
// vwa.isUnique("hello");
// vwa.isUnique("anotherWord");

Java:

public class ValidWordAbbr {

    public ValidWordAbbr(String[] dictionary) {
        for(int i = 0; i < dictionary.length; ++i) 
        { 
            String word = dictionary[i]; 
            int length = word.length(); 
            String key = word; 
            if(length > 2)
            {
                StringBuilder sb = new StringBuilder();
                sb.append(word.charAt(0)).append(length-2).append(word.charAt(length-1));
                key = sb.toString();
            }
            List<String> val = store.get(key);
            if(val == null)
            {
                val = new ArrayList<String>();
                store.put(key, val);
            }
            val.add(word);
        }
    }

    public boolean isUnique(String word) {
        String key = word;
        int length = word.length();
        if(length > 2)
        {
            StringBuilder sb = new StringBuilder();
            sb.append(word.charAt(0)).append(length-2).append(word.charAt(length-1));
            key = sb.toString();
        }
        List<String> val = store.get(key);
        if(val == null) return true;
        for(String s : val)
            if(!s.equals(word))
                return false;
        return true;
    }
    Map<String, List<String>> store = new HashMap<String, List<String>>();
}


// Your ValidWordAbbr object will be instantiated and called as such:
// ValidWordAbbr vwa = new ValidWordAbbr(dictionary);
// vwa.isUnique("Word");
// vwa.isUnique("anotherWord");