首先看一下矩阵的初始状态。
我们需要在这个矩阵中寻找目标字符串 bfce,第一步要做的就是先匹配上目标字符串的第一个元素 b ,我们从矩阵的第一行第一列的元素开始匹配,找到了 a 。
目标字符串为 bfce,此时查找第一个元素为 a ,与目标字符串的第一个元素 b 不相同,需要在四个方向搜索,看看能不能找到符合要求的元素,我们按照上左下右的顺序进行遍历寻找。
上:越界了左:越界了下:是 s ,与目标元素 b 不相同右:是 b,符合要求,依葫芦画瓢找第二个元素
上:越界了左:是 a,与目标元素 f 不相同下:是 f,与目标元素 f 相同,符合要求,依葫芦画瓢找第三个元素
上:根据题目要求不需要考虑左:是 s,与目标元素 c 不相同下:是 d,与目标元素 c 不相同右:是 c,与目标元素 c 相同,符合要求,依葫芦画瓢找第四个元素
上:是 c,与目标元素 e 不相同左:根据题目要求不需要考虑下:是 e,与目标元素 e 相同,符合要求,寻找结束,匹配成功,返回 true
2、规律
1、在搜索过程中,如果当前元素与目标元素不匹配,则回退到之前的节点再搜索2、在搜索过程中,如果当前元素与目标元素相匹配,则按照上左下右的方向进行再次搜索匹配剩下的元素3、在搜索过程中,搜索当前元素的上左下右方向的元素时,会出现重复访问之前元素的情况,比如搜索匹配成功的第三个元素 c 的四个方向时,会重复访问一下 f。
为了保证不重复访问节点,可以将这条路径上已经访问过的节点,修改为不在 word 当中的一个字符,保证以后再次访问时不会重复访问,这里我们将其修改为特殊字符 # 。
修改完后会出现一种情况,当前的节点元素与目标元素相匹配,但是在它的四个方向的节点中都找不到可以匹配到目标下一元素的节点。
比如此时当前元素 c 与目标元素 c 相匹配,但是目标下一元素为 x,而在当前元素的四个方向上都找不到 x ,需要把这个点回退,根据之前的操作,当前的节点被修改为了 #,所以为了能够回退成功,再回退操作时需要重新将 # 修改回原来的元素。 3、匹配
栈与队列:来看看栈和队列不为人知的一面栈与队列:我用栈来实现队列怎么样?栈与队列:用队列实现栈还有点别扭栈与队列:系统中处处都是栈的应用栈与队列:匹配问题都是栈的强项栈与队列:有没有想过计算机是如何处理表达式的?栈与队列:滑动窗口里求最大值引出一个重要数据结构栈与队列:求前 K 个高频元素和队列有啥关系?栈与队列:总结篇!