回溯法——面试题矩阵中的路径(一)

回溯法介绍

1.1
回溯法是蛮力法的升级版它从解决问题每一步的所有可能选项里系统的选择一个可行的解决方案。
1.2
回溯法非常适合由多个步骤组成的问题并且每个步骤都有多个选项。当我们在某一步做出一个选择时就进到下一步了如果不符合题目条件就回溯到原来的步骤进行新的选择如果这步的选择还没有符合条件的直到选到符合题目条件的选项为止。如果都不符合的话就会再回溯到上一步然后进入再进行新的选择就这样重复选择直到到达最终的状态。
1.3
通常回溯法算法适合用递归实现代码当我们到达某一个节点时尝试所有可能的选项并在满足条件的前提下递归地抵达下一个节点。

回溯法应用实例化

回溯法应用试题

题目:
请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格那么该路径不能再次进入该格子。
例如在下面的3*4的矩阵中包含一条字符串“"bfce”的路径(路径中的字母用下画线标出)。但矩阵中不包含字符串“abfb”的路径因为字符串的第一个字符b占据了矩阵中的第弟个格子之后路径不能再次进入这个格子。

分析回溯法解决问题过程
第一行第二个字母‘b’和路径‘bfce’的第一个字符相等所以从b开始分析b有3种选择向左到达字符a,向右到达字符t向下到达字符f。
如果假如第一次向左走会到达a但是a不是路径中的第二个字符所以会回溯到b再次重新选择直到有一次到达f才会继续向下走
在结点f也有3种选择如果我们选择了向左到达字符c但是之后再从左边的字符c走后发现无论怎么走都不可能到达字符c所以只能向回回溯到达字符f再重新选择。一直类推直到组成字符串bfce。
思路
首先在矩阵中任选一个格子作为路径的起点。假设矩阵中某个格子的字符为ch, 并且这个格子将对应于路径上的第i个字符。
如果路径上的第i个字符不是ch那么这个格子不可能处在路径上的第i个位置。
如果路径上的第i个字符正好是ch那么到相邻的格子寻找路径上的第i+1个字符。
除矩阵边界上的格子之外其他格子都有4个相邻的格子。重复这个步骤直到路径上所有字符都在矩阵中找到相应的位置。
由于回溯法的递归特性路径可以看成一个栈当在矩阵中定位了路径中前n个字符的位置之后在与第n个字符对应的格子的周围都没有找到第n+1个字符这时候只好在路径上回到第n-1个字符重新定位第n个字符。
由于路径不能重复进入矩阵的格子所以还需要定义和字符矩阵大小一样的布尔值矩阵用来标识路径是否已经进入到每个格子。

当矩阵中坐标为(row,col)的格子和路径字符串中下标为pathLength的字符一样时从4个相邻的格子(row,col-1)、(row-l,col)(row col+1)和(row+1,col)中去定位路径字符串中下标为pathLengh+1的字符。
如果4个相邻的格子都没有匹配字符串中下标为pathLengh+1的字符则表明当前路径字符串中下标为pathLengh的字符在矩阵中的定位不正确我们需要回到前一个字符(pathLengh-1)然后重新定位。
一直重复这个过程直到路径字符串上的所有字符都在矩阵中找到合适的位置(此时str[pathLength]==‘\0’)。