An abbreviation of a word follows the form
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
Assume you have a dictionary and given a word, find whether its abbreviation is unique in the dictionary. A word's abbreviation is unique if no other word from the dictionary has the same abbreviation.
Example:
Given dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true
这道题让我们求独特的单词缩写，但是题目中给的例子不是很清晰，来看下面三种情况：
1. dictionary = {"dear"}, isUnique("door") -> false
2. dictionary = {"door", "door"}, isUnique("door") -> true
3. dictionary = {"dear", "door"}, isUnique("door") -> false
从上面三个例子可以看出，当缩写一致的时候，字典中的单词均和给定单词相同时，返回 true。这里需要用 HashMap 来建立缩写形式和其对应的单词的映射，把所有缩写形式的相同单词放到一个 HashSet 中，然后再判断是否 unique 的时候只需要看给定单词的缩写形式的 HashSet 里面该单词的个数是否和 HashSet 中的元素总数相同，相同的话就是上面的第二种情况，返回 true。需要注意的是由于 HashSet 中不能有重复值，所有上面第二种情况只会有一个 door 存在 HashSet 里，但是并不影响判断结果，参见代码如下：
解法一：
class ValidWordAbbr {
public:
ValidWordAbbr(vector
for (auto a : dictionary) {
string k = a;
if (a.size() > 2) k = a[0] + to_string(a.size() - 2) + a.back();
m[k].insert(a);
}
}
bool isUnique(string word) {
string k = word;
if (word.size() > 2) k = word[0] + to_string(word.size() - 2) + word.back();
return m[k].count(word) == m[k].size();
}
private:
unordered_map
};
如果我们想省一些空间，也可以不用 HashSet，但如何区分上面的第二和第三种情况呢，在遇到 HashMap 中没有当前缩写形式的时候，将该缩写形式和当前单词建立映射，如果该缩写形式应经存在，那么看如果映射的单词不是当前单词，将映射单词改为空字符串，这样做的原因是，在对于第三种情况 dictionary = {"dear", "door"} 时，遍历 dear 时，建立 d2r 和 dear 的映射，当遍历到 door 的时候，由于 door 和 dear 不同，将映射改为 d2r 和 "" 映射，而对于第二种情况 dictionary = {"door", "door"}，保留 d2r 和 door 的映射，那么这样在判断 door 是否 unique 时，就可以区别第二种和第三种情况了，参见代码如下：
解法二：
class ValidWordAbbr {
public:
ValidWordAbbr(vector
for (auto a : dictionary) {
string k = a;
if (a.size() > 2) k = a[0] + to_string(a.size() - 2) + a.back();
if (m.find(k) != m.end() && m[k] != a) m[k] = "";
else m[k] = a;
}
}
bool isUnique(string word) {
string k = word;
if (word.size() > 2) k = word[0] + to_string(word.size() - 2) + word.back();
return m.find(k) == m.end() || m[k] == word;
}
private:
unordered_map
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/288
类似题目：
Two Sum III - Data structure design
Generalized Abbreviation
参考资料：
https://leetcode.com/problems/unique-word-abbreviation/
https://leetcode.com/problems/unique-word-abbreviation/discuss/73133/8-lines-in-C%2B%2B...
https://leetcode.com/problems/unique-word-abbreviation/discuss/73143/Java-Solution-with-One-HashMaplessString-Stringgreater-beats-90-of-Submissions
LeetCode All in One 题目讲解汇总(持续更新中...)
发表评论