从2D字符数组中打印所有可能的单词

Question

最近偶然发现了这个面试问题,

给定一个二维字符数组和一个可以及时搜索单词的字典O(1).需要打印字典中存在的数组中的所有单词.Word可以在任何方向形成,但必须在数组的任何边缘结束.(不用担心字典)

输入:

a f h u n
e t a i r
a e g g o
t r m l p

输出:

after
hate
hair
air
eat
tea

注意:这里"egg"不是字典单词,因为它不在数组的边缘结束.

我以前见过类似的问题,但从来没有想过一个好的算法来解决这些问题.有关如何处理这些问题(从字符数组中形成单词)的任何帮助都将非常有用.

(我能想到的唯一方法是找到2D数组中所有可能的字符排列,并检查它是否在数组的边缘结束,并检查排列是否是O(1)中字典中的有效字时间)

Answer 1

将数组转换为图，以便每个单元格[i,j] 与其 4 个邻居中的每一个单元格共享一条边[i+1,j], [i-1,j], [i,j+1], [i,j-1]。然后在每个数组边缘单元运行 DFS，并不断检查字典中是否有反向单词。