网格中的面试准备单词

Question

我一直在做面试准备问题，这是一个我遇到麻烦的问题，因为我不确定如何实现这个解决方案。这就是设置。你得到了一个8x8的字母网格和一个单词列表，你必须返回列表中最长的单词，这个单词可以从网格上的一个字母开始，然后像国际象棋中的骑士一样在网格中移动。例如，如果您有列表"word“、"string”、"test“和以下网格：

Y W E Z T N U W
O P A A C Q G F
T E L Z X C V B
N M M W F R T O
U I O N A S D F
B E J O L Z V C
T B N M Q W E R
T A S G X Z R S

然后你会返回"test"，因为这可以通过从网格左下角的“T”开始，向上跳两个，向右一个得到“E”，向下跳两个，向右一个得到“S”，然后向左两个，向上一个得到“T”，其他单词都不能在这个网格上形成。

我认为你会使用分支定界算法，但我完全不知道如何设置它。有人能帮上忙吗？我正在尝试用python实现。

注意:字母可以在网格中重复，即您可以任意多次跳转到同一字母上。

Answer 1

我的解决方案是:对于数组中的每个单词，迭代矩阵以找到第一个字母，然后可以对第一个字母的邻居(在本例中是骑士可以跳到的8个位置)使用呼吸优先搜索(BFS)或深度优先搜索(DFS)来查看它们是否匹配。您可以分别使用队列或堆栈迭代地实现BFS或DFS。