字符串的排列

题目分析:

1. 首先题目中的字典序已经表明了结果是需要排序的;
2. 结果中不能包含重复的字符串. 如果字符串中出现重复的字符, 比如: abbc, 那么在输出结果中像abbc,bacb这样的结果只能出现一次.

思路:
step1: 假设提取某一个字符之后, 剩下的子串可以用diGui(subStr)得到它的字典序的所有排列, 那么加上这个提取的字符作为首字符之后, 就得到了一组结果;
step2: 对于当前递归层, 给出的一个字符串, 只需要遍历所有字符, 分别提取所有没有提取过的字符做为首字符, 分别与剩下的子串拼接并加入到结果集中, 最后就可以得到想要的结果.

代码如下:

```java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Solution {

public ArrayList<String> Permutation(String str) {
    if (str==null || str.length()==0) return new ArrayList<>();
    char[] chars = str.toCharArray();
    Arrays.sort(chars);
    return diGui(new String(chars));
}
private ArrayList<String> diGui(String str){
    ArrayList<String> result = new  ArrayList<>();
    if(str.length() == 1){
        result.add(str);
        return result;
    }

    Set<Character> pickChars = new HashSet<>();
    for(int i = 0; i < str.length(); i++){
        // 遍历字符串, 从其中挑出第i个字符作为开头, 拼上剩下的字符串的字典排序结果
        // 不要挑重复的字符
        if(pickChars.add(str.charAt(i))){
            ArrayList<String> newResult = diGui(str.substring(0,i)+str.substring(i+1));
            for (String s : newResult) result.add(str.charAt(i) + s);
        }
    }
    return result;
}

}