字元串的排列Java

刷題記錄第22題，上一題：資料流中的中位數，本題位址：字元串的排列。

題目描述：

輸入一個字元串，列印出該字元串中字元的所有排列。

你可以以任意順序傳回這個字元串數組，但裡面不能有重複元素。

示例:

輸入：s = "abc"
輸出：["abc","acb","bac","bca","cab","cba"]
           

限制：

1 <= s 的長度 <= 8

這道題是一道典型的回溯法問題。在之前的八皇後問題的部落格中也采用了回溯的思想。

在算法小抄的一書中說到：解決一個回溯問題，實際上就是一個決策樹的周遊過程，且這個算法做的過程很基礎，就是窮舉過程。

• 路徑：也就是已經做出的選擇；
• 選擇清單：也就是目前可做出的選擇；
• 結束條件：也就是到達決策樹底部，無法再做出選擇的條件；

回溯算法的代碼架構如下：

private void backtrack(路徑， 選擇清單){
    if 滿足結束條件{
        result.add(路徑)
        return
    }
    
    for 選擇 in  選擇清單{
        做選擇
        backtrack(路徑， 選擇清單)
        撤銷選擇
    }
}
           

其核心也就在于，再

for

循環的遞歸，在遞歸調用前做出選擇，在遞歸調用結束後撤銷選擇。

本題中輸入的字元串，沒有明确說明是否是每個字母隻出現一次，是以這裡的字母其實可以出現多次。也就是比如

aaa

這樣的字元串。

解決該問題的一種較為直覺的思路是，我們首先生成所有的排列，然後進行去重。而另一種思路是我們通過修改遞歸函數，使得該遞歸函數隻會生成不重複的序列。

class Solution {
    private List<String> list;
    boolean[] vis;
    public String[] permutation(String s) {
        list = new ArrayList<>();
        vis = new boolean[s.length()];
        backtrack(s.toCharArray(), 0, s.length(), new StringBuffer());

        // 去重
        HashSet<String> strings = new HashSet<>(list); // List<String> list;
        String[] res = new String[strings.size()];
        int idx = 0;
        for (String string : strings) {
            res[idx++] = string;
        }
        return res;
    }
	
	// i 表示目前位置，n表示字元串長度
    private void backtrack(char[] arr, int i, int length, StringBuffer stringBuffer) {
        if(i == length && stringBuffer.length() > 0){
            list.add(stringBuffer.toString());
            return;
        }
        for (int j = 0; j < length; j++) {
            if(vis[j])
                continue;
            vis[j] = true;
            stringBuffer.append(arr[j]);
            backtrack(arr, i + 1, length, stringBuffer);// 探測下一個位置
            stringBuffer.deleteCharAt(stringBuffer.length() - 1);
            vis[j] = false;
        }
    }
}
           

另一種，在遞歸函數中去重的思路為：在遞歸函數中設定一個規則，保證在填每一個空位的時候重複字元隻會被填入一次。具體地，我們首先對原字元串排序，保證相同的字元都相鄰，在遞歸函數中，我們限制每次填入的字元一定是這個字元所在重複字元集合中「從左往右第一個未被填入的字元」，即如下的判斷條件：

if (vis[j] || (j > 0 && !vis[j - 1] && s[j - 1] == s[j])) {
    continue;
}