1,回溯算法解决
字符串的排列其实就是排列组合,我们可以把它想象成为一棵n叉树(n是s的长度),然后每一个节点都要从字符串中选择一个字符,但注意不能选择重复的,比如在一个节点选择了a,那么他的子孙节点都不能再选择a了
作者:sdwwld
链接:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/shu-ju-jie-gou-he-suan-fa-hui-su-suan-fa-11gk/
来源:力扣(LeetCode)
java
private void backtrack("原始参数") { //终止条件(递归必须要有终止条件) if ("终止条件") { //一些逻辑操作(可有可无,视情况而定) return; } for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) { //一些逻辑操作(可有可无,视情况而定) //做出选择 //递归 backtrack("新的参数"); //一些逻辑操作(可有可无,视情况而定) //撤销选择 } }
入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]
这里只需要按照这个模板对他稍作修改即可,代码如下
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; } }