字符串的排列

题目描述

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 输入描述: 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路

递归：(基于回溯法)即先固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，再次递归获得首位后面的字符串组合。 若是过程中遇到重复值，比如当前首位字母为A，下一位字母也为A，则不交换.(即使交换了也一样。) 那么如何判断之前的字符串中有没有存在当前字母呢？ 可以选择使用HashSet，来自动判断当前的Set中有没有重复。 经典图示： 避坑提示： 1.在每个分支进行完后，一定要将交换过的元素复位，避免影响其他分支。 2.因为有“Swap A with A”这样的操作，并且题目指出可能有字符重复，所以分支末尾可能有重复的序列，在加入ArrayList要进行去重判断，不重复再加入。

/**
本题把字符串分为两部分：part1是字符串的被固定的最后一个字符，part2是被固定的最后一个字符以后的所有字符。
第一步是（for循环、交换操作）
目的是求所有可能出现在第一个位置的字符，即把第一个字符和后面所有字符交换。
第二步是采用递归
固定住第一个字符，求后面所有字符的排列。
而“求后面所有字符的排列”这一步就可以按照上面的思路递归进行。
需要字符串转换为字符数组，使用toCharArray（）方法
**/
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
          
   
    public ArrayList<String> Permutation(String str) {
          
   
        ArrayList<String> res = new ArrayList<>();
        if(str == null || str.length() == 0){
          
   
            return res;
        }
         permu(str.toCharArray(),0,res);
         Collections.sort(res);
         return res;
    }
    public void permu(char[] chars,int index,ArrayList<String> list){
          
         
        if(index == chars.length-1){
          
   //去重，当递归交换到最后一个位置的时候，就看看list有么有这个字符串，没有的话就放进去。
            String val = String.valueOf(chars);
            if(!list.contains(val)){
          
   
                list.add(val);
            }
        }else{
          
   //循环来执行交换操作，先交换，然后固定这个，下一个交换。
          for(int i = index;i < chars.length;i++){
          
   //注意这里一定是index，而不是index+1，否则会有遗漏元素
              swap(chars,index,i);
              permu(chars,index+1,list);//依次固定一个,注意固定的是index
              swap(chars,index,i);//最后一定要交换回来不要影响之后的执行
           }
        }       
        //return list;
    }    
    public void swap(char[] chars,int i ,int j){
          
   
        char temp = chars[i];
        chars[i] = chars[j];
        chars[j] = temp;       
    }
}