题目链接
牛客网在线oj题——字符串的排列
题目描述
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。
题目示例
示例1
输入：
“ab”
返回值：
[“ab”,“ba”]
说明：
返回[“ba”,“ab”]也是正确的
示例2
输入：
“aab”
返回值：
[“aab”,“aba”,“baa”]
示例3
输入：
“abc”
返回值：
[“abc”,“acb”,“bac”,“bca”,“cab”,“cba”]
示例4
输入：
“”
返回值：
[“”]
解题思路
这道题可以使用深度优先搜索和回溯来将所有的情况列出来，然后将符合条件的过程集添加到结果集中
首先定义ArrayList< String> result，作为最后返回的结果集。
定义Stack< Character> path，作为递归过程中生成的过程集。
定义boolean[] isUsed，判断当前位置是否使用过
实现深度递归函数PermutationDFS(char[] chars, int depth, Stack< Character> path, boolean[] isUsed, ArrayList result)，参数分别为str对应的char数组，递归深度depth，过程集path，标志是否遍历过的isUsed数组，结果集result
递归的终止条件是：当递归深度等于chars的长度，将其构造为字符串，添加到结果集result中
创建一个循环，从0到chars的长度 - 1，代表排列的起始位置，如果当前位置用过了（isUsed[i] == true），那么就continue
向过程集中添加当前元素chars[i]，将该位置标志为已遍历(isUsed[i] = true),然后继续递归，让递归深度加一
当递归返回到当前位置时，应该回溯到未开始递归的状态，将isUsed[i] = false,删除过程集当前元素
最后创建一个HashSet，将所有result中的元素添加到HashSet中，防止添加重复的序列
完整代码
import java.util.*;
public class Solution {public ArrayList<String> Permutation(String str) {ArrayList<String> result = new ArrayList<>();if(str != null && str.length() > 0){Stack<Character> path = new Stack<>();boolean[] isUsed = new boolean[str.length()];PermutationDFS(str.toCharArray(), 0, path, isUsed, result);HashSet<String> hashSet = new HashSet<>();for (int i = 0; i < result.size(); i++){hashSet.add(result.get(i));}ArrayList<String> newResult = new ArrayList<>(hashSet);Collections.sort(newResult);return newResult;}return result;}private void PermutationDFS(char[] chars, int depth, Stack<Character> path, boolean[] isUsed, ArrayList<String> result) {if(depth == chars.length){ArrayList<Character> tmp = new ArrayList<>(path);StringBuilder stringBuilder = new StringBuilder();for (int i = 0; i < tmp.size(); i++){stringBuilder.append(tmp.get(i));}result.add(stringBuilder.toString());return;}for (int i = 0; i < chars.length; i++){if(isUsed[i]){continue;}path.add(chars[i]);isUsed[i] = true;PermutationDFS(chars, depth + 1, path, isUsed, result);isUsed[i] = false;path.pop();}}
}
