526互联

回溯算法：剑指 Offer 38. 字符串的排列

发布时间 2023-04-24 11:38:53作者: ZDREAMER

题目描述：

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

限制：

　　1 <= s 的长度 <= 8

 

 

class Solution{
    Set<String> res = new HashSet<>();
    public String[] permutation(String s){
        backTrack(s.toCharArray(),new StringBuilder(),new boolean[s.length()]);
        return res.toArray(new String[0]);
    }
    // 回溯函数
    public void backTrack(char[] ch,StringBuilder sb,boolean[] used){
        // 终止条件
        if(sb.length()==ch.length){
            res.add(sb.toString());
            return;
        }
        // 选择列表
        for(int i=0;i<ch.length;i++){
            // 剪枝，如果当前位置的元素已经使用过，则跳过进入下一个位置
            if(used[i]) continue;
            // 更新标记
            used[i]=true;
            // 做出选择
            sb.append(ch[i]);
            // 进入下层回溯
            backTrack(ch,sb,used);
            // 撤销选择
            sb.deleteCharAt(sb.length()-1);
            used[i]=false;
        }
    }
}

 

 

什么是回溯法

回溯法也可以叫做回溯搜索法，它是一种搜索的方式。回溯是递归的副产品，只要有递归就会有回溯。

 

回溯法解决的问题

回溯法，一般可以解决如下几种问题：

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

（组合无序，排列有序）

 

如何理解回溯法

回溯法解决的问题都可以抽象为树形结构，所有回溯法的问题都可以抽象为树形结构！

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

 

 

回溯法模板

  • 回溯函数模板返回值以及参数

回溯算法中函数返回值一般为void。

再来看一下参数，因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

void backtracking(参数)

　　

  • 回溯函数终止条件

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

if (终止条件) {
    存放结果;
    return;
}

　　

  • 回溯搜索的遍历过程

回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

 

for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
}

　　

for循环就是遍历集合区间，可以理解一个节点有多少个孩子，这个for循环就执行多少次。

backtracking这里自己调用自己，实现递归。

backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法模板框架如下：

 

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

 

　　

toArray()

ArrayList提供了一个将List转为数组的一个非常方便的方法toArray，在使用toArray方法时，我们在参数列表中传入new String[0] 表示这个方法将返回一个String类型的字符串。

List<String> list = new ArrayList<>();
String[] strs = list.toArray(new String[0]);

　　

toString()

StringBuilder类的toString()方法是一种内置方法，用于返回表示StringBuilder对象包含的数据的字符串。

创建并初始化一个新的String对象，以从该StringBuilder对象获取字符序列，然后由toString()返回String。 Object包含的对该序列的后续更改不会影响String的内容。

以下示例程序旨在说明StringBuilder.toString()方法：

 

s.toCharArray()

1.toCharArray()的用法:是将字符串对象中的字符转换为一个字符数组;

String s="I am niuandidog";

char  arr[ ]=s.toCharArray( );

System.out.println(arr);

//output:

I am niuandidog

 

Stringbuilder 用法

StringBuilder 类在 Java 5 中被提出，它和 StringBuffer 之间的最大不同在于 StringBuilder 的方法不是线程安全的（不能同步访问）。

由于 StringBuilder 相较于 StringBuffer 有速度优势，所以多数情况下建议使用 StringBuilder 类。