兄弟单词这个题目最初见于《编程珠玑》，但是里面给出的方法是最笨的，一般不提倡采用吧；这个题目在之前的百度面试中也遇到过，本文实现两种方法的代码，方法如下：
方案一：使用数据结构 map<key,list>。兄弟单词共用一个签名key，key为单词内部排序后的词条，list存储同一key的单词集合；相对于编程珠玑中的方法，该方法在空间上节省了每个单词一个key的空间；在时间上，不再需要二分查找，O(1)的查找；但是这种方法还可以优化，见方案二
方案二：使用trie树。trie树又称字典树，在面试题中关于"字符串"与"数字串"类型的问题中高频出现，非常实用。对于兄弟单词，兄弟单词公用一个key自不必说，只是trie的节点结构应该多出一个域list，用来存储key对应的兄弟单词；具体节点结构应该为
Read full article from 兄弟单词 — 两种算法实现 | 勇幸|Thinking
No comments:
Post a Comment