1.给定一个单词a,如果通过交换单词中字母的顺序可以得到另外的单词b,那么定义b是a的兄弟单词。现在给定一个字典,用户输入一个单词,如何根据字典找出这个单词有多少个兄弟单词?
这里有一种很原始的办法,变换所有的单词,得到所有的兄弟单词,然后依次在字典中寻找。可想而知这是很复杂的
基于上面的思想我们对字典进行优化。不妨将字典建成一个hash链表。使得字典中的兄弟单词有相同的key例如 hello 我们选取key为ehllo,这里的key
选取依据是单词中的字母从小到大排列。这样我们就用链表将所有兄弟单词都串在了一起。从而将字典构成了一个hash链表。
开始遍历字典,将每个单词按照key,加入到对应的链表中。当需要取兄弟单词时,只需取这个单词的key,然后到相应的链表中取查找。
这样创建hash_map时间复杂度为O(n),查找单词的时间复杂度为O(1)
2关于字符串哈希函数
关于字符串如何转key