输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
\n
👍 391👎 0
题解
看起来有点面熟，很直白的深度搜索回溯算法。
根据所给字符串s，挨个位置遍历，在新得出的字符串的每一位上穷举，并记录已举过的字符串，在穷举的时候，如果已经存在于已使用过的位置的集合的记录中，则跳过。
而最终要求“里面不能有重复元素”，所以最终的结果集用set集合保存，直接进行去重。
class Solution {
private HashSet<String> list;
private Integer length;
public String[] permutation(String s) {
list = new HashSet<>();
length = s.length();
HashSet<Integer> visited = new HashSet<>();
dfs(s.toCharArray(),visited,0,new char[s.length()]);
return list.toArray(new String[0]);
}
private void dfs(char[] charArr,HashSet<Integer> visited,int index,char[] newCharArr){
if (index==length){
list.add(new String(newCharArr));
return;
}
for (int i = 0; i < charArr.length; i++) {
if (visited.contains(i)){
continue;
}
visited.add(i);
newCharArr[index] = charArr[i];
dfs(charArr,visited,index+1,newCharArr);
visited.remove(i);
}
}
}
结果
解答成功:
执行耗时:69 ms,击败了10.93% 的Java用户
内存消耗:44.2 MB,击败了21.26% 的Java用户
而在结果集没有使用set集合的时候，跑这样一个用例出了问题。
测试用例:"aab"
测试结果:["aab","aba","aab","aba","baa","baa"]
期望结果:["aba","aab","baa"]
所以，取第一个a还是第二个a是没有区别的，这边之前记录的是HashSet<Integer> visited字符串的索引位置，所以在此之外，可以再借助一个字符串集合进行剪枝操作Set<Character> sameChar。剪枝之后的结果集也可以不用set集合了，直接更简单的List集合替代。
另外还有一点小小的改动，一开始写的visited是Set集合，而记录内容是某个索引位置是否访问过，都知道索引的特征是从0-N连续的，这边可以再简化成一个boolean[] visited数组。
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
private List<String> list;
private Integer length;
public String[] permutation(String s) {
list = new ArrayList<>();
length = s.length();
boolean[] visited = new boolean[s.length()];
dfs(s.toCharArray(),visited,0,new char[s.length()]);
String[] res = new String[list.size()];
int i = 0;
for (String s1 : list) {
res[i] = s1;
i++;
}
return res;
}
private void dfs(char[] charArr,boolean[] visited,int index,char[] newCharArr){
if (index==length){
list.add(new String(newCharArr));
return;
}
Set<Character> sameChar = new HashSet<>();
for (int i = 0; i < charArr.length; i++) {
if (visited[i]){
continue;
}
if (sameChar.contains(charArr[i])){
continue;
}
sameChar.add(charArr[i]);
visited[i] = true;
newCharArr[index] = charArr[i];
dfs(charArr,visited,index+1,newCharArr);
visited[i] = false;
}
}
}
//leetcode submit region end(Prohibit modification and deletion)
解答成功:
执行耗时:14 ms,击败了64.61% 的Java用户
内存消耗:42.7 MB,击败了73.19% 的Java用户
