1. 题目描述
输入一个字符串,按字典序打印出该字符 串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
2. 输入描述
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
3. 题目分析
- 经典的一道全排列算法的题目
- 全排列算法
- 这里以A{a,b,c}为例，来说明全排列的生成方法，对于这个集合，其包含3个元素，所有的排列情况有3!=6种，对于每一种排列，其第一个元素有3种选择a,b,c，对于第一个元素为a的排列，其第二个元素有2种选择b,c；第一个元素为b的排列，第二个元素也有2种选择a，c，……，依次类推，我们可以将集合的全排列与一棵多叉树对应。如下图所示
4. 题目代码
public ArrayList<String> Permutation(String str) { ArrayList<String> strings = new ArrayList<String>(); if (str == null || str.length() == 0) { return strings; } char[] string = str.toCharArray(); perm(strings, string, 0, string.length - 1); Collections.sort(strings); return strings; } public static void perm(ArrayList<String> strings, char[] a, int k, int m ) { if (k == m) { String str = String.valueOf(a); if (strings.contains(str) == false) { strings.add(str); } } else { /* * 进入时 */ for (int i = k; i <= m; i++) { swap(a, i, k); perm(strings, a, k + 1, m); // 回溯 swap(a, i, k); } } } public static void swap(char[] a, int x1, int x2) { char temp; temp = a[x1]; a[x1] = a[x2]; a[x2] = temp; }
