当前位置 博文首页 > 数据结构和算法：剑指 Offer-字符串的排列
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
视频链接
看到这里我们很容易想到的一种解决方式就是回溯，具体可以看下《450，什么叫回溯算法，一看就会，一写就废》，之前我们总结回溯算法的时候有一个经典的模板
private void backtrack("原始参数") {
//终止条件(递归必须要有终止条件)
if ("终止条件") {
//一些逻辑操作（可有可无，视情况而定）
return;
}
for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
//一些逻辑操作（可有可无，视情况而定）
//做出选择
//递归
backtrack("新的参数");
//一些逻辑操作（可有可无，视情况而定）
//撤销选择
}
}
这里只需要按照这个模板对他稍作修改即可，代码如下
public String[] permutation(String s) {
Set<String> res = new HashSet<>();
backtrack(s.toCharArray(), "", new boolean[s.length()], res);
return res.toArray(new String[res.size()]);
}
private void backtrack(char[] chars, String temp, boolean[] visited, Set<String> res) {
//边界条件判断，当选择的字符长度等于原字符串长度的时候，说明原字符串的字符都已经
//选完了
if (temp.length() == chars.length) {
res.add(temp);
return;
}
//每一个节点我们都要从头开始选
for (int i = 0; i < chars.length; i++) {
//已经选择过的就不能再选了
if (visited[i])
continue;
//表示选择当前字符
visited[i] = true;
//把当前字符选择后，到树的下一层继续选
backtrack(chars, temp + chars[i], visited, res);
//递归往回走的时候要撤销选择
visited[i] = false;
}
}
