这是我在电话采访中被问到的另一个问题:
给定一个字典和一个填字游戏(字符的二维矩阵)找到所有可以在填字游戏中找到的字典单词。
我所能想到的就是对字典进行哈希处理，在填字游戏中找到每个可能的单词并搜索哈希。我无法全部优化。
必须承认微软的面试问题很难 :(
请给我思考的台词。
最佳答案
怎么样:
- 为字典构建搜索树(每个字母一层)
- 对于网格中的每个位置，开始在索引中搜索，一次一个字符，并在每个允许的方向上继续，直到索引中没有剩余条目，或者您到达网格边界
我认为散列在这里不是非常有用的优化。
关于algorithm - 如何在字母矩阵中找到单词，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4313971/