An abbreviation of a word follows the form <first letter><number><last letter>. Below are some examples of word abbreviations:
a) it --> it (no abbreviation) 1 ↓ b) d|o|g --> d1g 1 1 1 1---5----0----5--8 ↓ ↓ ↓ ↓ ↓ c) i|nternationalizatio|n --> i18n 1 1---5----0 ↓ ↓ ↓ d) l|ocalizatio|n --> l10n Additionally for any string s of size less than or equal to 2 their abbreviation is the same string s.
Find whether its abbreviation is unique in the dictionary. A word's abbreviation is called unique if any of the following conditions is met:
- There is no word in
dictionary
such that their abbreviation is equal to the abbreviation ofword
. - Else, for all words in
dictionary
such that their abbreviation is equal to the abbreviation ofword
those words are equal toword
.
Example 1:
Input ["ValidWordAbbr", "isUnique", "isUnique", "isUnique", "isUnique"] [[["deer", "door", "cake", "card"]], ["dear"], ["cart"], ["cane"], ["make"]] Output [null, false, true, false, true] Explanation ValidWordAbbr validWordAbbr = new ValidWordAbbr(["deer", "door", "cake", "card"]); validWordAbbr.isUnique("dear"); // return False validWordAbbr.isUnique("cart"); // return True validWordAbbr.isUnique("cane"); // return False validWordAbbr.isUnique("make"); // return True
Constraints:
- Each word will only consist of lowercase English characters.
A:
就是简单的 用 hashmap
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 | class ValidWordAbbr { public: ValidWordAbbr(vector<string>& dictionary) { for(auto & s : dictionary){ if(s.length()<=2){ M[s].push_back(s); }else{ string key = string(1,s[0]) + to_string(s.length()-2) + string(1,s.back()); M[key].push_back(s); } } } bool isUnique(string word) { string key = word; if(word.length()>2){ key = string(1,word[0]) + to_string(word.length()-2) + string(1,word.back()); } if(M.find(key) == M.end()){ // not find return true; } for(auto& tmp : M[key]){ if(tmp != word) return false; } return true; } private: unordered_map<string, vector<string>> M; }; /** * Your ValidWordAbbr object will be instantiated and called as such: * ValidWordAbbr* obj = new ValidWordAbbr(dictionary); * bool param_1 = obj->isUnique(word); */ |
No comments:
Post a Comment