问题描述:输入是由一些字母和单词构成的二维数组,目标是找出字谜中的单词,这些单词可以是水平、垂直或沿对角线以任何方向放置。找出二维数组中所有的单词。
作为例子,如下所示的字谜由单词 this 从第一行第一列的位置即(1,1)处开始并延伸至(1,4);单词 two 从(1,1)到(3,1);fat 从(4,1)到(2,3);而 that 则从(4,4) 到(1,1)。
思路
第一种:对单词表中的每个单词,我们检查每一个有序三元组(行,列,方向),验证是否有单词存在。但坏处是这将导致大量嵌套的for循环。
第二种:对于每一个尚未进行到字谜最后的有序四元组(行,列,方向,字符数)我们可以测试所指的单词是否在单词表中。这也导致使用大量嵌套的for循环。如果在任意单词中的最大字符数已知的情况下,那么该算法有可能节省一些时间。
代码实现: