前言

回溯法可以看成蛮力法的升级版。它会搜遍问题的解空间，试图找到一个符合约束条件的解决方案。回溯法非常适合由多个步骤组成的问题，并且每个步骤都有多个选项。当我们在某一步选择了一中一个选项时，就进入下一步，然后有面临新的选项。我们就这样重复选择，直至到达最终的状态。

而这样的选择过程非常适合用树结构来表示。在某一步有 n 个可能的选项，那么把该步骤看出树状结构中的一个节点，每个选项就看出树中节点连接线，经过这些连接线到达该节点的 n 个子节点，再选定符合的子节点到达下一步骤。树的叶节点对应着终结状态。如果叶节点的状态满足题目的约束条件，那么我们找到了一个可行的解决方案。

如果在叶节点的状态不满足约束条件，那么需要回溯到上一节点再尝试其他的选项。如果上一节点所有可能的选项都已经尝试过，仍满足不了题目的约束条件，则再次回溯到上一节点。如果所有选项都已经尝试过仍然不能到达满足约束条件的终结状态，则该问题无解。

题目(矩阵中的路径）

题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。例如 a b c e s f c s a d e e 矩阵中包含一条字符串”bcced”的路径，但是矩阵中不包含”abcb”路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路

首先，由于可以在矩阵中任意选择一个格子作为路径的起点，因此首先应该遍历矩阵的每个位置作为可能的起点。然后，假设矩阵中的某个格子上的字符为ch，并且字符串的第 i 个位置也为字符 ch，那么就到相邻的格子寻找字符串中第 i+1 位置上的字符。如果该格子上的字符与字符串的第i个路径上的字符不同，则跳过该格子。重复以上过程，直至字符串中的字符都在矩阵中相应位置出现。另外，需要定义 bool 矩阵标识路径是否已经进过每个格子。

当矩阵中坐标为(row,col)的格子和路径字符串中下标为pathLength的字符一样时，从4个相邻的格子(row,col-1),(row-1,col),(row,col+1)和(row+1,col)中去定位字符串中下标为pathLength+1的字符。
如果都没有匹配到，则需要回到前一个字符(pathLength-1)，重新定位。

重复这个过程，直到遇到’\0’。

算法实现

复杂度分析

时间复杂度

首先hasPath中有两层循环，耗时O(rowsxcols),接着每个格子最多需要判断周围 4 个格子是否为路径的下一个字符，时间复杂度O(4xrowsxcols)。因此最后的时间复杂度为O(rows^2xcols^2)。可能分析的不是很对，请指教。

空间复杂度

建立了一个辅助空间布尔矩阵，空间复杂度为O(rowsxcols)。假设字符长度为n，则递归栈需要O(n)的空间，但最大的复杂度还是O(rowsxcols)。

参考

<<剑指offer2>>