剑指 offer 笔记 27 | 字符串的排列

题目描述
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串 abc , acb , bac , bca , cab 和 cba。

输入描述:

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路分析
借牛客网大神的解题思路
分两种情况，一种是有重复值情况，固定第一个字符，递归取得首位后面的各种字符串组合；再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合，如图所示

第二种是有重复值情况，假设 abb，第一个数 a 与第二个数 b 交换得到 bab，然后考虑第一个数与第三个数交换。

此时由于第三个数等于第二个数， 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！

import java.util.ArrayList;
import java.util.List;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        List<String> resultList = new ArrayList<>();
        if(str.length() == 0)
            return (ArrayList)resultList;
        fun(str.toCharArray(),resultList,0);
        Collections.sort(resultList);
        return (ArrayList)resultList;
    }
     
    private void fun(char[] ch,List<String> list,int i){
        if(i == ch.length-1){
          //判断一下是否重复
            if(!list.contains(new String(ch))){
                list.add(new String(ch));
                return;
            }
        }else{
                for(int j=i;j<ch.length;j++){
                           swap(ch,i,j);
                           fun(ch,list,i+1);
                           swap(ch,i,j);
                         }
                  }
           }

    //交换数组的两个下标的元素
    private void swap(char[] str, int i, int j) {
            if (i != j) {
                char t = str[i];
                str[i] = str[j];
                str[j] = t;
            }
        }
    }

链接：https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
来源：牛客网