算法/數據結構來確定一個單詞是否是一個有效的英文單詞

我正在設計一個HTML5遊戲，要求我驗證用戶輸入的單詞是否是有效的英文單詞。我知道我可以通過發送單詞到服務器來執行驗證，但是，由於我想按用戶類型進行驗證，因此服務器端驗證不是最佳解決方案。因此我需要在遊戲中執行驗證，並在用戶的瀏覽器中運行。算法/數據結構來確定一個單詞是否是一個有效的英文單詞

對我來說，驗證用戶輸入的單詞的最有效方法是什麼？用戶輸入的單詞是否對英語中的每個單詞都有效？

一個trie？隨着用戶的輸入，可以逐字逐句完成。 – jwimberley

「以用戶類型進行驗證」是什麼意思？你的意思是，如果用戶輸入「th」，你不採取任何行動，因爲有詞以「th」開始，但如果用戶輸入「f」，那麼你會以某種方式通知他輸入無效，因爲有沒有英文單詞以「thf」開頭？ –

不需要。驗證意味着無論當前顯示的用戶類型是否被驗證，以確定它是否是有效的單詞。屏幕指示符將隨着用戶輸入而不斷更新。當該單詞無效時它將顯示紅色，而當該單詞有效時它將顯示綠色。因此，您可能會遇到這樣的情況：用戶輸入時，指示器可能會多次在紅色和綠色之間切換，具體取決於輸入的單詞。 –

是的，你可以使用數據結構，如trie，我們在那裏製作可搜索單詞的樹，並找到O(|P|)時間的元素。如果你問自己，爲什麼是一個更好的選擇..你會看到每當用戶一次輸入一個字符時，你可以在飛行中逐字地遍歷並根據你的遊戲規則給出快速反饋。

P: pattern you are searching for.

而且你說的服務器端驗證是不可能的，但我所看到的比賽裏，他們讓Ajax調用來驗證的話，在那個時候，他們創造一些東西，在屏幕上或一些遊戲故事或上彈出組件，以使您感覺到它正在發生即時或以某種有趣的方式發生，

2017-08-23 16:54:46 coderredoc

儘管trie是「理論上正確」的數據結構，但我的計算機上的/ usr/share/dict/words只能在1 MB以下。有zlib的純JS實現可用於解壓縮。一個二進制搜索算法將花費20個電話來查找字典中的任何特定單詞，這足以在瀏覽器中交互使用。

這足以在瀏覽器中實現這一點。

2017-08-23 17:49:58 btilly

這樣的任務的好算法是Bloom filter。你應該知道，難的部分將是組裝一本合適的字典。

2017-08-23 19:09:20 user448810

您需要描述如何使用布隆過濾器來解決這個問題，並且還需要解決誤報問題。 –

回答