string - 如何在表格中查找单词？

Question

这是一个编码练习。假设有一个字母表和一些单词。我必须找到表格中单词的位置。单词可以在表格中的任何位置开始，并且可以垂直或水平定向。 (我们可以假设一行/一列可能只包含一个词)。

例如:

table = xabcx        xxxdx        xxfexwords = ["abc", "edc", "fe"]expected output is (0,1), (2,3), (2,2)

直接的解决方案是遍历所有行/列并检查每行/列是否包含任何单词。它需要 O(列数 * 行数 * 字数 * 字长)。有更好的解决方案吗？也许我应该预处理单词列表以构建更高效的数据结构？

Answer 1

可以使用Trie 数据结构来存储表。一旦有了 Trie，查词就非常容易了。