这是一个编码练习。假设有一个字母表和一些单词表。我必须在表格中找到单词的位置。一个单词可以从表中的任何位置开始，并且可以垂直或水平地定向。 （我们可以假定一行/列可能只包含一个词）。如何在表格中查找单词？
例如：
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）。