如何找出字典中的兄弟單詞

給定一個單詞a，如果通過交換單詞中字母的順序可以得到另外的單詞b，那么定義b是a的兄弟單詞。現在給定一個字典，用戶輸入一個單詞，如何根據字典找出這個單詞有多少個兄弟單詞？

首先定義一個key，使得兄弟單詞有相同的key，不是兄弟的單詞有不同的key。例如，將單詞按字母從小到大重新排序后作為其key，比如bad的key為abd，good的key為dgoo。
使用鏈表將所有兄弟單詞串在一起，hash_map的key為單詞的key，value為鏈表的起始地址。
開始時，先遍歷字典，將每個單詞都按照key加入到對應的鏈表當中。當需要找兄弟單詞時，只需求取這個單詞的key，然后到hash_map中找到對應的鏈表即可。
這樣創建hash_map時時間復雜度為O(n)，查找兄弟單詞時時間復雜度是O(1)。

key也可以這樣這樣構造，每個字母對應不同的素數，而單詞以每個素數的乘積作為key

也可以不用hash_map，如果是海量詞典的話，可以用B+樹

轉自：http://hi.baidu.com/mianshiti/blog/item/33590e3786e89c305bb5f592.html

總結

以上是生活随笔為你收集整理的兄弟单词的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。