算法--字符串的排列

       今天做了一个算法题目，当时没做出来，参考了一下网上的答案，虽然说弄明白了怎么回事，但是感觉下次遇到了可能还是会做不出来，所以先把解题思路记下来，以后时常回顾一下。

题目描述：

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

输入描述:

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

解题思路：

    这是一道经典的DFS题目，利用回溯的思想找到一个字符数组的全排列，并完成去重与字典序排序操作。
    大致思想便是，先确定第i个字符（从i到最后完成遍历枚举），然后对i+1-N-1个字符递归使用全排列（缩小范围），这便是dfs。
    但因为DFS过程必须向后序递归过程传递剩下的字符，那么如何传递呢？
    每一次确定字符后，将剩余字符装入一个容器中，传递下去。但这样会增加许多拷贝遍历操作，极其麻烦。
    另一种方法，便是将确定的字符与当前第 i个字符相交换，然后i+1-N-1依然是剩下的字符。
    但是要注意，这样做改变了字符数组，必须进行完一次dfs过程后，将数组复原，便于确定i位置其他元素时，不会受到影响。

 

如何完成去重？ 

      从图中可以发现，只要每一层确定的字符不一样，那么便不会出现重复元素，换句话说，只要每一次递归枚举确定i元素时，不出现重复的即可，这可用set实现，这比上述方法，提前去重，避免了后序很多无谓的递归。

代码实现：

import java.util.*;
public class Solution {
    public ArrayList<String> Permutation(String str) {
        ArrayList<String> result = new ArrayList<String>();
        if (str == null || str.length() == 0) {
            return result;
        }
        char[] chArray = str.toCharArray();
        findPerutation(result, chArray, 0);
        Collections.sort(result);
        return result;
    }
    private void findPerutation(ArrayList<String> result, char[] chArray, int i) {
        if (i == chArray.length) {
            result.add(new String(chArray));
            return;
        }
        HashSet<Character> set = new HashSet<Character>();
        for (int j = i; j < chArray.length; j++) {
            if (set.contains(chArray[j])) {
                continue;
            }
            set.add(chArray[j]);
            // 交换
            swap(i, j, chArray);
            // 递归
            findPerutation(result, chArray, i + 1);
            // 还原顺序
            swap(i, j, chArray);
        }
    }
    private void swap(int i, int j, char[] chArray) {
        if (i == j) {
            return;
        }
        char temp = chArray[i];
        chArray[i] = chArray[j];
        chArray[j] = temp;
    }
}

参考连接：

https://blog.csdn.net/zjxxyz123/article/details/79709240