字符串所有排列组合暴力递归
字符串所有排列组合暴力递归
gzq大数据
发布于 2021-11-24 13:28:21
发布于 2021-11-24 13:28:21
代码可运行
运行总次数：0
代码可运行
给你一个字符串"acb"，可以打印出六种排列组合，这里又是一种index推动的递归，但是这里有一些小trick，就是从第一个开始，在后面的字符串的每一个字符进行交换，这样就可以省很多空间，在数组内原地交换，遍历到每一个字符上也有很多细节，将后面的每一个字符和当前字符进行交换，并且每次遍历完一个，这个字符就不要在动了，随后再还原现场。
public static void main(String[] args) {
String input = "abz";
HashSet<String> res = new HashSet<>();
printAllPermutation(input, res);
for (String re : res) {
System.out.println(re);
}
}
private static void printAllPermutation(String input, HashSet<String> res) {
char[] sChars = input.toCharArray();
process(sChars, 0, res);
}
private static void process(char[] sChars, int index, HashSet<String> res) {
if (index == sChars.length) {
res.add(new String(sChars));
return;
}
for (int j = index; j < sChars.length; j++) {
swap(sChars, index, j);
process(sChars, index + 1, res);
swap(sChars, index, j);
}
}
private static void swap(char[] sChars, int index, int j) {
char tmp = sChars[index];
sChars[index] = sChars[j];
sChars[j] = tmp;
}改进:加入缓存，因为每次交换过来的这个字符如果一样的话，后面结果是相同的,没必要再排列了
public static void main(String[] args) {
String input = "abz";
HashSet<String> res = new HashSet<>();
printAllPermutation(input, res);
for (String re : res) {
System.out.println(re);
}
}
private static void printAllPermutation(String input, HashSet<String> res) {
char[] sChars = input.toCharArray();
process(sChars, 0, res);
}
private static void process(char[] sChars, int index, HashSet<String> res) {
if (index == sChars.length) {
res.add(new String(sChars));
return;
}
boolean[] cache = new boolean[26];
for (int j = index; j < sChars.length; j++) {
if (!cache[sChars[j] - 'a']) {
cache[sChars[j] - 'a'] = true;
swap(sChars, index, j);
process(sChars, index + 1, res);
swap(sChars, index, j);
}
}
}
private static void swap(char[] sChars, int index, int j) {
char tmp = sChars[index];
sChars[index] = sChars[j];
sChars[j] = tmp;
}本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021/11/20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
