Firefox centos java 微软 Python 程序员 php Windows wordpress shell 开源 apache 编程 mysql 云计算 Android Ubuntu linux nginx google

快速上手:在字典中查找单词

一個單詞如果交換其所含字母順序,得到的單詞稱為兄弟單詞,例如mary和army是兄弟單詞,即所含字母是一樣的,只是字母順序不同,用戶輸入一個單詞,要求在一個字典中找出該單詞的所有兄弟單詞,並輸出。給出相應的數據結構及算法。要求時間和空間復雜度盡可能。
給定一個單詞a,如果通過交換單詞中字母的順序可以得到另外的單詞b,那麽定義b是a的兄弟單詞,例如單詞army和mary互為兄弟單詞。現在給定一個字典,用戶輸入一個單詞,如何根據字典找出這個單詞有哪些兄弟單詞?要求時間和空間效率盡可能的高。

解法一:
使用hash_map和鏈表。 
首先定義一個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)。
 
解法二:
同樣使用hash_map和鏈表。
將每一個字母對應一個質數,然後讓對應的質數相乘,將得到的值進行hash,這樣兄弟單詞的值就是一樣的了,並且不同單詞的質數相乘積肯定不同。
使用鏈表將所有兄弟單詞串在一起,hash_map的key為單詞的質數相乘積,value為鏈表的起始地址。
對於用戶輸入的單詞進行計算,然後查找hash,將鏈表遍歷輸出就得到所有兄弟單詞。
這樣創建hash_map時時間復雜度為O(n),查找兄弟單詞時時間復雜度是O(1)。

延伸阅读

  • 抱歉,暂无相关内容!

评论