这是一个编码练习。假设有一个字母表和一些单词。我必须找到表格中单词的位置。单词可以在表格中的任何位置开始,并且可以垂直或水平定向。 (我们可以假设一行/一列可能只包含一个词)。
例如:
table = xabcx xxxdx xxfex words = ["abc", "edc", "fe"] expected output is (0,1), (2,3), (2,2)
直接的解决方案是遍历所有行/列并检查每行/列是否包含任何单词。它需要 O(列数 * 行数 * 字数 * 字长)
。有更好的解决方案吗?也许我应该预处理单词列表以构建更高效的数据结构?
最佳答案
可以使用Trie 数据结构来存储表。一旦有了 Trie,查词就非常容易了。
关于string - 如何在表格中查找单词?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/8872480/