這是一個編碼練習。假設有一個字母表和一些單詞表。我必須在表格中找到單詞的位置。一個單詞可以從表中的任何位置開始，並且可以垂直或水平地定向。 （我們可以假定一行/列可能只包含一個詞）。如何在表格中查找單詞？
例如：
table = xabcx
xxxdx
xxfex
words = ["abc", "edc", "fe"]
expected output is (0,1), (2,3), (2,2)
的簡單的解決辦法是循環遍歷所有行/列的，並檢查是否每行/列中包含任何的話。它需要O(number of columns * number of rows * number of words * word length)。有更好的解決方案嗎？也許我應該預處理單詞列表以建立更高效的數據結構？
我會建議一個表的二叉樹結構。這基本上是大多數主要的關係數據庫系統使用的。在這種情況下，可以基於從單詞創建的一些整數哈希碼來平衡樹。然後，在搜索時，從搜索項中創建一個散列，並智能地遍歷您的樹，直到找到匹配的行。
您可以使用Trie數據結構來存儲表格。一旦你擁有Trie，查詞很容易。
這是一個簡單的方法。
你只是在尋找完全匹配，所以我認爲你應該立即考慮基於散列的算法，而不是基於樹的。首先考慮將字母表中的每個字母與其在表格中的位置相關聯的散列圖。現在爲每個單詞，你看第一個字母，然後遍歷表（左，右，上，下）以查看整個單詞是否存在。
您可以通過改爲每個方向（左，右，上，下）的每兩個字母組合（僅676個鍵）創建一個哈希映射來改善此問題。現在，您首先檢查您的單詞的前兩個字母，並且哈希映射會立即爲您提供這兩個字母存在的位置。您現在可以繼續在該方向查看該表以查看該單詞是否已完成。或者，您可以選取該單詞的下兩個字母，然後查看該字母對的位置是否與第一個字母對相鄰並具有相同的方向。
通過考慮每個方向的每個三個字母組合的散列圖，您可以進一步改進...。您應該能夠根據啓發式方法（如平均字長）在存儲要求和性能之間找到一個很好的平衡點。
在每一列/行上使用Aho–Corasick string matching algorithm只需要O（number of columns * number of rows + length of patterns + number of output matches）。