JZ38 字元串的排列

描述

輸入一個長度為 n 字元串，列印出該字元串中字元的所有排列，你可以以任意順序返回這個字元串數組。
例如輸入字元串ABC,則輸出由字元A,B,C所能排列出來的所有字元串ABC,ACB,BAC,BCA,CBA和CAB。

題目主要信息
給定一個長度為n的字元串，求其中所有字元的全排列
字元串中可能有重覆字元，列印順序任意
字元串中只包含大小寫字母

思路

都是求元素的全排列，字元串與數組沒有區別，一個是數字全排列，一個是字元全排列。為了便於去掉重覆情況，還是參照數組全排列，優先考慮字典序排序，因為排序後重覆的字元就會相鄰，後序遞歸找起來也很方便
使用臨時變數去組裝一個全排列情況：每當我們選取一個字元以後，就確定了其位置，相當於對字元串中剩下的元素進行全排列添加在該元素的後面，給剩餘部分進行全排列就是一個子問題，因此可以使用遞歸。

終止條件：臨時字元串中選取了n個元素，已經形成了一種排列情況，可以將其加入輸出數組中。
返回值：每一層給上一層返回的就是本層級在臨時字元串中添加的元素，遞歸到末尾的時候，就能添加全部元素

具體做法

先對字元串按照字典序排序，獲得第一個排列情況

準備一個空串，暫存遞歸過程中組裝的排列情況。使用額外的vis數組用於記錄哪些位置的字元被加入了

每次遞歸從頭遍歷字元串，獲取字元加入：首先根據vis數組，已經加入的元素不能再加入了；同時，如果當前的元素str[i]與同一層的前一個元素str[i-1]相同，且str[i-1]已經用，也不需要將其加入

進入下一等遞歸前將vis數組當前位置標記為使用過

回溯時，需要修改vis數組當前位置標記，同時去掉剛剛加入的字元串元素

臨時字元串長度達到原串長度就是一種排列情況

代碼

package mid.JZ38字元串的排列;

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {

    private StringBuilder builder = new StringBuilder();

    private ArrayList<String> res = new ArrayList<>();

    public ArrayList<String> Permutation(String str) {

        if (str == null || str.length() == 0) {
            return res;
        }

        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String sortedStr = new String(chars);

        //當vis[i]=0，表示index為0的字元沒有被使用
        //當vis[i]=1，表示index為1的字元被使用了
        int[] vis = new int[chars.length];

        dfs(sortedStr, vis, 0);

        return res;
    }

    private void dfs(String str, int[] vis, int depth) {

        if (builder.length() == str.length()) {
            res.add(builder.toString());
            return;
        }

        for (int i = 0; i < str.length(); i++) {
            if (vis[i] == 1) {
                continue;
            }
            //當前的元素str[i]與同一層的前一個元素str[i-1]相同且str[i-1]已經用過了
            if (i != 0 && str.charAt(i) == str.charAt(i - 1) && vis[i - 1] == 1) {
                continue;
            }
            builder.append(str.charAt(i));
            vis[i] = 1;
            dfs(str, vis, depth + 1);
            builder.deleteCharAt(builder.length() - 1);
            vis[i] = 0;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().Permutation("ab"));
    }
}