Skip to content

Latest commit

 

History

History

048. Group Anagrams

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
 
 
 
 
 
 

这道题本身没有任何难度,但因为题目描述的不好,会让人非常迷惑。

我建议不明白看完题目不知道题目在说什么的童鞋好好读读这个帖子

说白了,这道题是让我们摘出 Anagrams,什么是 Anagrams? 就是相同字母,但不同组合的单词。如 dog 与 god 这样的。

更具体的说,就是输入的数组里,如果出现 Anagrams, 则保留,如果孤苦伶仃,没有互为 Anagrams 的单词,就删掉。从而组成输出。

明白了题意,这道题就不足为奇了,如果一堆单词互为 Anagrams, 那么将他们统统排个序,肯定是完全相同的单词。这便是此题的核心思想了。

想要知道 Anagrams 出现几次,我们显然希望有一个分别计数的工具,对于一个 key (Anagrams 排序后相同的那个单词), 对应某个 value, 最好能标注出现多少次。

不需要犹豫,这一定是 Hash 表的干活,在 C++ 中,是 unordered_map 的干活。


分析到这里,基本知道了解法,只不过为了更加高效,我希望能在一次迭代中搞定。那么如何定义 Hash 表的 value 很重要。

我们来整理一下逻辑:

  • 如果 key 出现两次, ret.push_back(current_string);
  • 如果 key 只出现一次, 显然应该置之不理

但问题在于,你不完整的迭代一次,如何能知道哪个 key 只出现一次?但反过来呢?我不关心哪个 key 只出现一次,只关心哪个 key 重复了,不就行了?

一旦重复,我 push 进入返回 vector, 并将第一次的单词也 push 进入返回 vector, 但要避免重复将第一次的单词 push, 需要做个标记。最好用一个无效值作为标记。

当我们用迭代器迭代 vector 的时候,最佳的天然无效值便是 end() 迭代器,如果已经将第一次的单词 push 过了,那么将这个 key 的 value 标记为 end(),下次发现是无效值,便无需再重复 push.

于是,我们就可以在一次迭代中完成整个逻辑了。