题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述：
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
import java.util.ArrayList;
public class Solution {
public ArrayList<String> Permutation(String str) {
}
}
参考思路： 递归回溯
-
我们先固定第一个字符，然后递归取得首位后面的各种字符串组合；
-
再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合；
-
递归的出口，就是到了最后一个字符的时候，判断结果集中是否有相同的字符串，没有的话就插入到结果集中，有的话则不插入。
参考实现：
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if (str != null && str.length() > 0) {
PermutationHelper(str.toCharArray(), 0, result);
Collections.sort(result);
}
return result;
}
public void PermutationHelper(char[] ch, int i, ArrayList<String> list) {
//如果已经是最后一个字符了，则判断是否插入到结果集中
if (i == ch.length - 1) {
//将字符数组转换为字符串
String value = String.valueOf(ch);
//如果结果数组中没有相同的字符串则插入到结果集中
if (!list.contains(value)) {
list.add(value);
}
}else {
for (int j = i; j < ch.length; j++) {
//交换两个位置上的字符
swap(ch, i, j);
//将交换位置后的继续递归调用
PermutationHelper(ch, i + 1, list);
//将交换的两个字符还原
swap(ch, i, j);
}
}
}
public void swap(char[] ch, int i, int j) {
char temp = ch[i];
ch[i] = ch[j];
ch[j] = temp;
}
}
附录：
String 类方法
char[] toCharArray() //将此字符串转换为一个新的字符数组。
static String copyValueOf(char[] data) //返回指定数组中表示该字符序列的 String。
看完之后，如果还有什么不懂的，可以在评论区留言，会及时回答更新。
这里是猿兄，为你分享程序员的世界。
非常感谢各位大佬们能看到这里，如果觉得文章还不错的话，
求点赞👍 求关注💗 求分享👬求评论📝
这些对猿兄来说真的 非常有用！！！
注： 如果猿兄这篇博客有任何错误和建议，欢迎大家留言，不胜感激！
京公网安备 11010502036488号