剑指offer - 字符串的排列(Java实现)

题目链接：https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&&tqId=11180&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路：首先我们可以将其进行全排列：我们将第一个位置固定不变，然后对后面的字符串进行全排列，后面的子字符串也可以遵循这种思想，所以我们可以使用递归的思想来完成代码的编写，将第一个位置的字符与所有的字符交换一次作为第一个位置的固定值，然后对后面的字符串进行全排列，通过下面写出的全排列可以发现，如果按照这种方式进行全排列，我们无法保证其结果是按照字典序进行输出的，所以我们可以使用 Java 提供的类库对 ArrayList 按照字典排序，然后返回即可。当然这里还涉及到去重的问题，具体可以见代码中的处理。

• "abc"
• "acb"
• "bac"
• "bca"
• "cba"
• "cab"

  import java.util.*;
  public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> list = new ArrayList<>();
        if(str == null || str.length() == 0) return list;
        int n = str.length();
        char[] chars = str.toCharArray();
        solve(0, chars, list);
        Collections.sort(list, new Comparator<String>() {//对最终结果按照字典序排序
            public int compare(String s1, String s2) {
                return s1.compareTo(s2);
            }
        });
        return list;
    }
    public static void solve(int n, char[] chars, ArrayList<String> list) {
        if(n == chars.length) {
            list.add(String.valueOf(chars));
            return ;
        }
        for(int i = n; i < chars.length; ++ i) { //固定一个位置,剩下的字符串继续进行全排列
            if(n != i && chars[n] == chars[i]) continue; //如果遇到相同的字符则不进行交换
            Swap(n, i, chars);
            solve(n + 1, chars, list);
            Swap(n, i, chars);
        }
    }
    public static void Swap(int x, int y, char[] chars) {
        char temp = chars[x];
        chars[x] = chars[y];
        chars[y] = temp;
    }
  }