题解 | #字符串的排列#

JZ27

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

参考的是一叶浮jian的题解 ，进行了一些修改
思路上主要是采用递归的方式实现动态规划
需要注意的是题干上要求按照字典顺序打印出，我采用了Collections.sort()实现。
字段顺序的部分可以最后return前再进行处理，之前需要把字符串的所有排序可能输出出来，具体思路如下：
比如输入字符串"abc"，则fun(abc)=

1. a+fun(bc)
2. b+fun(ac)
3. c+fun(ab)
   同理，以fun(bc)为例
   fun(bc)=
4. b+fun(c)
5. c+fun(b)
   其中fun(c)=c, fun(b)

如果输入的字符串有相同的字符，如"aab"，则从中拿出字符时，相同的字符只能拿出一次：
fun(aab)=

1. a+fun(ab)
2. b+fun(aa)

最终代码如下：

import java.util.ArrayList;
import java.util.Collections;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        // 题目要求按字典顺序输出，所以这里需要排序
        ArrayList<String> result = recursionPermutation(str);
        Collections.sort(result);
        return result;
    }

    public ArrayList<String> recursionPermutation(String str){
        ArrayList<String> result = new ArrayList<String>();
        if(str.length() == 1){
            result.add(str);
            return result;
        }
        // 开始进行递归
        for(int i = 0; i < str.length(); i++){
            //进行复制，不更改原输入
            StringBuilder strBuilder = new StringBuilder(str);
            ArrayList<String> subResult;
            if(i ==0 || strBuilder.charAt(0) != strBuilder.charAt(i)){
                // 交换索引0与i处的字符
                char temp = strBuilder.charAt(i);
                strBuilder.setCharAt(i, strBuilder.charAt(0));
                strBuilder.setCharAt(0, temp);
                subResult = recursionPermutation(strBuilder.substring(1));
                //对下层递归结果进行处理
                for(int j = 0; j < subResult.size(); j++){
                    result.add(temp + subResult.get(j));
                }
            }
        }
        return result;
    }
}

String和StringBuilder的常见用法

//String的用法：
//java中String是只读的，没有办法进行变换，因此需要使用StringBuilder。
String.length() //获取字符串的长度
String.charAt(i) //获取第i个字符的内容
String.subString(start)   //获取[start,）的字符串
String.subString(start,end) //获取[start,end）中的字符串
char[] c = iniString.toCharArray() //将字符串转为char数组来进行改变字符内容
String.equal() //判断两个字符串是否相等

//StringBuilder的用法：
除了String中支持的方法外，StringBuilder支持字符的增、删、改。
stringBuilder.append("we");  //添加we在词尾
stringBuilder.insert(0,"we");//在0的位置加入后面的内容
stringBuilder.delete(0,1);  //删除[0,1)的数据
stringBuilder.deleteCharAt(0);
stringBuilder.setCharAt(0,'p'); //在某一个独特位置设置字符
char c = stringBuilder.charAt(i);//查询某个位置上的字符
System.out.println(stringBuilder);
new String(stringBuilder);//用stringBuilder来初始化String