[討論] 檢查任意的字母組合能拼成哪些字

[mander (阿平)]

各位好，第一次發文
這個問題有一些基本的想法提出來與大家討論效果的優劣

我想要輸入一組任意的字母組合(想是 C L E A R E H )
字母組合中不考慮順序、大小寫，字母可能出現多次(E出現兩次)
程式檢查有哪些單字能用上面列出的字母組合拼出來


例如以上的組合可能會跑出如clear,hear,reel,real,heal,rec...的列表


現在已經產生一個字典檔dic.txt了
請問各位會怎麼考慮寫這個查詢的程式呢?


現把小弟粗略的想法提出來
想法挺簡單的，就先建一個可供查詢的索引，再查是否單字在其中

A.建索引

1.字典檔中每個單字都建編號
2.對每個字母(a-z)，建一個參照表
  檢查單字中出現了哪些字母，在參照表中加入有出現單字的整數編號W(k)

B.查詢

1.查詢的時候把輸入字串中包含哪些字母，將字母參照表中的W(k)
  放到一個array A或hash H中，
  是在hash中的話key-valur pair的key是W(k)，value則每符合一個字母就加一

2.對hash H依照value排序(這裡會有問題value值可能不唯一)
  然後照value值大小輸出W(k)

3.印出W(k)對應的單字

以上想法實在始有夠簡單，感覺在查詢的時候效率會很差
hash H在遇到字母AEIOU這種的時候會變大很多

邊寫的時候發現以上其實就是invertd file & boolean search的做法 XD
只是是字母版的

希望能夠拋磚引玉，有更好的想法一起討論




--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 59.104.108.136
推 threecia:已經有字典檔, 直接對檔案內容做過濾不是更快嗎?
→ threecia:反正你會產生的單字也逃不出這個字典檔的範圍
→ mander:的確 因為母音的重疊範圍過大 直接掃瞄所有內容會比
→ mander:較快 預先做索引的好處便消失了