作者:whisper
链接:https://www.proprogrammar.com/article/913
声明:请尊重原作者的劳动,如需转载请注明出处
输入一个字符串,打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。
示例:
输入:s = "abc" 输出:["abc","acb","bac","bca","cab","cba"]
限制:
1 <= s 的长度 <= 8
难度:中等;标签:回溯算法;编程语言:JAVA
class Solution {
// 题解中的解法:https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation2(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复,因此剪枝
set.add(c[i]);
swap(i, x); // 交换,将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
做过类似的,忘了,题解中的方法,思路很清晰,把每个不同的数分别放在第一位,第二位,第。。。。,如果没有重复的数,第一位有n种情况,第二位有n-1种情况,。。。。,因为可能有重复,所以用set去重,swap的意思是第i位原来的数到后面,构成其它的情况,具体可以看题解方法
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202205 | 1 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论