回溯
2020-03-01 本文已影响0人
Gyu2233
image
简单说一下思路：我们求整个字符串的排列，可以看成两步。
first，求所有可能出现在第一个位置的字符，即把第一个字符和后面所有字符交换；
second，固定第一个字符，求后面所有字符的排列。
这时候，我们仍然是把后面的所有字符分成两部分：后面字符的第一个字符，以及这个字符之后的所有字符。
然后把第一个字符逐一和它后面的字符交换。（重复上面的操作而已）
矩阵中的路径
代码的简要思路如下：
1，根据给定数组，初始化一个标志位数组，初始化为false，每走过一个位置标识为true，不能走第二次；
2，根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge；
3，根据 i 和 j 先确定一维数组的位置，因为给定的matrix是一个一维数组（这个设定有点奇怪）；
4，确定递归终止条件： （1）越界；（2）当前矩阵值（字符）不等于对应位置的值（字符）；（3）已经走过了。都直接返回false；
5，如果k==length-1，说明待判定的字符串str已经判断到最后一位了，说明匹配成功了；
6，接下来，最重要的步骤来了——不断递归寻找四周的格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的下一个格子，直到 k==length-1 或 不满足递归条件 为止；
7，走到这里，说明此路不通，置为false回去再试。
类似题目
