输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
示例
输入
“ab”
返回值
[“ab”,“ba”]
动态规划的思想是将问题分解成子问题，从最小的子问题开始解，不断扩大子问题，并利用子问题的解来求解大问题，直到解出原问题。
对于字符串排列，最小的子问题是单个字符，它的排列就是它本身，然后不断在尾部增加字符，增加字符时利用上一个子问题的排列结果，例如假设当前问题是abc，它的子问题是ab的排列，假设我们已经知道ab的解是{ab, ba}，则在这个解的基础上插入新字符c，例如在解ab的基础上可以得到{cab, acb, abc}，同理在ba的基础上可以得到{cba, bca, cab}，最终得到问题abc的解为{cab, acb, abc, cba, bca, cab}，思路十分直观。
在实现的过程中，为了避免重复解的存在，使用一个HashMap来存储结果，自动去重，最后进行排序即可
public ArrayList<String> Permutation(String str) {
HashMap<String, Integer> hashMap = new HashMap<>();
int len = str.length(); // 获取字符串长度
hashMap.put(str.substring(0, 1), 1);
for (int i = 1; i < len; i++) {
HashMap<String, Integer> tmp = new HashMap<>();
String insert = str.substring(i, i + 1);
for (String s : hashMap.keySet()) {
// 在每个字符串中从前到尾插入当前字符
for (int j = 0; j < s.length() - 1; j++) {
String front = s.substring(0, j + 1), behind = s.substring(j + 1);
tmp.put(front + insert + behind, 1);
}
// 头和尾
tmp.put(insert + s, 1);
tmp.put(s + insert, 1);
}
hashMap = tmp;
}
ArrayList<String> res = new ArrayList<>();
for (String s : hashMap.keySet())
res.add(s);
// 排序
Collections.sort(res);
return res;
}
递归法的思想如下图（图片参考），将第一个字符与后面的字符交换，可以得到每个字符都在开头的所有情况，然后固定第一个字符，递归地去搜索
它的子字符串的解，子字符串同样是固定前面部分，此时则是交换第二个字符和后面的所有字符，并固定前两个字符，搜索它的子字符串的解；…
递归出口是当字符串只有一个字符时，此时就可以保存排列好的结果
在是实现时，由于需要频繁交换字符串中两个位置的值，因此先将String转换为char数组，在交换时更加高效，
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
PermutationHelper(str.toCharArray(), 0, res);
// 排序
Collections.sort(res);
for (String s : res)
System.out.print(s + " ");
return res;
}
public static void PermutationHelper(char[] str, int index, ArrayList<String> res) {
if (index == str.length - 1) {
// 若不重复则添加到结果中
if (!res.contains(String.valueOf(str))) res.add(String.valueOf(str));
return;
}
for (int i = index; i < str.length; i++) {
// swap index and i
swap(str, index, i);
PermutationHelper(str, index + 1, res);
swap(str, i, index); // 需要交换回来，不改变str的值
}
}
public static void swap(char[] str, int i, int j) {
char temp = str[i];
str[i] = str[j];
str[j] = temp;
}