递归--打印一个字符串的全部排列(java)

打印一个字符串的全部排列

自负串全排序:
举例:
abc 的全排序是:
abc
acb
bac
bca
cba
cab

解题思路

因为每个字符都要选,其实就是选择每个字符的顺序,那我们递归时,就可以把不同顺序一直递归下去.

代码演示

    /*** 字符串的全排列* @param str* @return*/public static List<String> allSubSequence(String str){if (str == null || str.equals("")){return null;}//保存答案ArrayList<String> ans = new ArrayList<>();process(str.toCharArray(),0,ans);return ans;}/*** 递归* @param str 字符串数组* @param index  下标值* @param ans 保存答案*/public static void process(char[]str, int index, List<String> ans){//base caseif (index == str.length){ans.add(String.valueOf(str));}else{for (int i = index;i < str.length;i++){//因为每个字符都要选,我们只是选择顺序,因此交换下顺序,swap(str,i, index);//然后递归process(str,index + 1,ans);//要把交换过的顺序 恢复回去,这样才能保证递归出全部顺序.swap(str,i,index);}}}

打印一个字符串的全部排列，要求不要出现重复的排列

解题思路:
我们可以按上面的代码去做,只需要用HashSet 去保存答案,就会去重了,但这样并没有优化效率,在递归时去掉可能会重复的值,这样才能把效率优化下来,
怎样优化呢:
两个相同的字符,如果已经有一个出现过在某个位置,那么剩下相同的字符也不用重复交换了,这样会提高效率
根据上面的思路,我们只需要加个判断,
因为字符转换成数字的值在0-255 ,因此用长度256 的数组就可以标记了,代码演示,

代码演示,

    /*** 打印一个字符串的全部排列，要求不要出现重复的排列* @param str* @return*/public static List<String> allSubSequence2(String str){if (str == null || str.equals("")){return null;}ArrayList<String> ans = new ArrayList<>();process2(str.toCharArray(),0,ans);return ans;}/*** 递归* @param str* @param index* @param ans*/public static void process2(char[]str, int index, List<String> ans){if (index == str.length){ans.add(String.valueOf(str));}else{//标记相同的字符是否交换过,boolean[] flag = new boolean[256];for (int i = index;i < str.length;i++){if (!flag[str[i]]){flag[str[i]] = true;swap(str,i, index);process(str,index + 1,ans);swap(str,i,index);}}}}

递归专题

递归–字符串的全部子序列和不重复的子序列（java）

递归–汉诺塔问题(java)