今天来聊聊回溯思想,
回溯,可以理解为后退或者返回上一层,
通常用法是:对于每处都有多种方向选择前进,当选择一种方向前进后,发现不能再继续前进的时候,就返回该处继续选择剩下的方向前进,
这样子的思想就称为回溯。
比如给定一个二维表,求到达某处的的路径数量,
如果该处不是在边界,那么对于该处来说,就有四个方向可选择,
通常我们结合深度优先搜索(DFS)来做,
DFS的好处就是一条路走到黑,不撞南墙不回头,
选定一个方向一直进行下去,当发现没有再进行下去的条件的时候,就开始回溯回来,继续选择剩下的三个方向继续DFS前进,
这个进行下去的条件一般会有两个,
- 该处是否被访问过了,这个我们一般借用一个标记数组来辅助
- 是否在边界,前进方向减少
当然有时候题目还会有其他条件,比如说障碍物等等。
以上就是对回溯的大概介绍,如果能够理解了上面,说明你大概对回溯有一定的认识了,
下面我们通过两道题目来认识一下回溯具体的实现,
单词搜索
给定一个二维网格和一个单词,找出该单词是否存在于网格中。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
示例:
1 | board = |
提示:
- board 和 word 中只包含大写和小写英文字母。
- 1 <= board.length <= 200
- 1 <= board[i].length <= 200
- 1 <= word.length <= 10^3
解题思路
这道题,我一开始没有看仔细,一拿到题目,就刷刷的开始写,用了两个HashTable,一个记录board中出现的字母数量,一个用来记录单词中字母的数量,主要判断两种数量是否一致就可以判断单词是存在在网格中。
以上是错误示范,因为题目有个很苛刻的条件,
单词必须按照字母的顺序,通过相邻的单元格内的字母构成,
有人可能一下子对“相邻“这个概念有点懵,题目也给出解释了,通俗来讲就是当前的上下左右四个方向,其他的都不行,
比如有一个测试案例
[‘a’, ‘b’], [‘c’, ‘d’]
求“abcd”的时候返回的是false,
这是因为,
[‘a’, ‘b’],
[‘c’, ‘d’]
b和c不在相邻位置,
理解这个很重要,因为这就是涉及到我们的回溯的思想,
回归到题目,
我们从网格的左上角开始,与单词从左到右的字母进行比较,
当该处符合的时候,就把这里标记成已访问,然后对四个方向进行进行dfs,
这时候就涉及到了一个知识,如何重置dfs的状态,
当对该点的四个方向都进行遍历后,发现并没有符合要求,那么此处的访问状态得改回未访问状态,为回溯做准备,
当符合要求的时候,就返回true;
下面以题目的事例进行图解说明:
查找 ABCCEE
搜索从左上角开始,
将单词从左到右进行对比,
此时匹配,但此时在边界,只有两个方向可以选择,先考虑右边,
右边匹配相等,此时还在边界,依旧只有两个方向,继续考虑右边,
此时匹配,和上面一样,继续考虑右边,
当前不匹配,此时回溯上一层,
从 “C” 处进行重新选择,之前在“C” 处选择了右边,此时只剩下下面,则往下面进行DFS,
此时匹配,上面已经标记被访问过,此时只剩下三个方向,先考虑右边,
当前不匹配,回溯上一层,
从 “C” 处进行重新选择,之前在“C” 处选择了右边,而上边又被访问过,此时只剩下下边和左边,先考虑下边,则往下面进行DFS,当前匹配,
此时在边界,只有两个方向选择,先考虑右边,此时匹配,则说明,从左上角(0,0)处出发,能找到一个单词,则返回true,如果不能,则从(0,1)开始继续DFS。
如果理解了上面,说明基本上已经搞定这道题了,
通过分析,我们需要几个东西:
四个方向的表示
标记数组(用于标记是否被访问)
DFS方法(用于对四个方向分别进行dfs)
判断边界的方法
通过这些,我们就可以一步步搭建起我们的代码。
代码
1 | class Solution { |
以上就是单词搜索的做法,采用回溯,一步一步的前进,遇到不对的,就回溯,返回上一层继续选择前进,直到把这条路走到黑,也就是把单词遍历完都没有找到,那就得重新选择开始点,直到把网格全部的点作为开始点尝试过,都没有的话,说明该网格中的字母找不到这个单词。
以上是单词搜索 I ,还有一个单词搜索 II,如果以上已经掌握了,下面这个就是加两句代码的事,来看看题,
单词搜索 II
给定一个二维网格 board 和一个字典中的单词列表 words,找出所有同时在二维网格和字典中出现的单词。
单词必须按照字母顺序,通过相邻的单元格内的字母构成,其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
示例:
1 | 输入: |
解题思路
相比于第一题,这道题寻找的不是一个单词,而是一组单词,
那很简单啊,只要从单词表中一个一个的取出来进行比较就行了,
这不就是第一题了吗?
所以掌握了上一题,这一题就是复制粘贴,
但这道题还是需要一个列表来保存结果的,
直接上代码吧。
代码
1 | class Solution { |
整理于2020.4.11,本文图片来源于liweiwei1419的题解,只为学习而用,侵删。