当前位置： 移动技术网 > IT编程>脚本编程>Python > LeetCode 288. 单词的唯一缩写（哈希）

LeetCode 288. 单词的唯一缩写（哈希）

2020年07月03日  | 移动技术网IT编程  | 我要评论

文章目录

1. 题目

一个单词的缩写需要遵循 <起始字母><中间字母数><结尾字母> 这样的格式。

以下是一些单词缩写的范例：

a) it                      --> it    (没有缩写)

     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

假设你有一个字典和一个单词，请你判断该单词的缩写在这本字典中是否唯一。
若单词的缩写在字典中没有任何 其他 单词与其缩写相同，则被称为单词的唯一缩写。

示例：
给定 dictionary = [ "deer", "door", "cake", "card" ]
isUnique("dear") -> false
isUnique("cart") -> true
isUnique("cane") -> false
isUnique("make") -> true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/unique-word-abbreviation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

容易错的例子

[[["hello"]],["hello"]]			[null,true]
[[["a","a"]],["a"]]				[null,true]
  • 长度小于等于2的直接true
  • 对转换后的 key 计数
class ValidWordAbbr {
	unordered_map<string, int> m;
    unordered_set<string> dict;
	string key;
public:
    ValidWordAbbr(vector<string>& dictionary) {
    	for(auto& d : dictionary)
    	{
            if(d.size()<=2)
                continue;
            m[getkey(d)]++;
            dict.insert(d);
        }
    }
    
    bool isUnique(string word) {
        if(word.size() <= 2)
            return true;
    	key = getkey(word);
    	if((dict.count(word) && (m[key] == 1)) || m.find(key) == m.end())
    		return true;
    	else
    		return false;
    }
    string getkey(string& word)
    {
    	key = word[0]+to_string(word.size()-2)+word[word.size()-1];
    	return key;
    }
};

296 ms 48.2 MB

长按或扫码关注我的公众号，一起加油、一起学习进步！
Michael阿明

本文地址：https://blog.csdn.net/qq_21201267/article/details/107092387

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网