數據結構在電話簿應用

Question

我想要存儲在電話簿， 聯繫人和我想的是，用戶將搜索只是名稱的一部分高效的子字符串搜索。

例如： 電話簿包含：

Tom, John, Eve, Barbi ,Johnathon. 

現在，「HN」的用戶搜索，其結果必須是「約翰」和「喬納森」。

我讀到TRIE，但其良好的只是前綴。

感謝

Answer 1

對於大多數人來說，他們的地址簿會在它不到1000個條目。你肯定可以通過在每個名字中依次搜索「hn」的子字符串來獲得。

喜歡的東西，在Python：

results = [name for name in address_book if name.contains(search_term)] 

Answer 2

如果我開發的項目，這將是我的解決方案;下面的代碼只是僞代碼，你可以在每一個編程語言

result; 
booklist; 
search_keyword; 
if(length(search_keyword) == 1) //people generaly types first char of the name to find him/his in their list. 
    for i=0 to n //traverse 0 to n 
     if(booklist[i][0] == search_keyword[0]) //check first letter with booklist element and search_keyword 
      result.push(booklist[i]); 

if(length(search_keyword) == 2) //people generaly types first two letter of the name to find him/his in their list. 
    for i=0 to n //traverse 0 to n 
     if(booklist[i][0] == search_keyword[0] AND booklist[i][1] == search_keyword[1]) //check first letter with booklist element and search_keyword 
      result.push(booklist[i]); 

if(length(search_keyword) > 2) 
    for i=0 to n //traverse 0 to n 
     if(booklist[i].contains(search_keyword)) 
      result.push(booklist[i]); 

return result; 

試試這個在這個算法，大多數用戶會等待O（n）的時間複雜度。

Answer 3

在電話簿中，通常情況下，

1. 的條目數量沒有那麼大。

2. 條目添加/刪除/修改，更經常比他們搜查。

我建議，因此，您維護一個哈希表映射到子在它們出現的條目列出。當條目被修改時，這個哈希表應該被修改。

例如，假設您添加長度爲ň一個新的條目。該條目最多有ň子。對於每一次這樣子：

1. 如果不是在哈希表中，添加一個條目的子映射到一個空列表。

2. 無論是否在哈希表中，都將此條目添加到子字符串對應的列表中（只要確保不添加兩次）。

如果你有米字，最長的單詞是ñ，然後O（m×n個）應該足以存儲一切。對於典型的電話簿，這很小。