輸入一個字串，按字典序列印出該字串中字符的所有排列，例如輸入字串 abc，則按字典序列印出所能排列出來的所有字串 abc，acb，bac，bca，cab，cba
解題思路
我們假設這么一個場景：
- 固定 A 為字串開頭，要知道以 A 開頭的組合有多少，則必須知道 A 之后的字串（B、C）能構成多少種組合
- 固定 B 為字串開頭，要知道以 B 開頭的組合有多少，則必須知道 B 之后的字串能構成多少種組合，但這時剩下的字符只有 C 了，所以得出一個組合就是 ABC
- 固定 C 為字串開頭，要知道以 C 開頭的組合有多少，則必須知道 C 之后的字串能構成多少種組合，但這時剩下的字符只有 B 了，所以得出一個組合就是 ACB
- 固定 B .....
可以發現這是一個遞回的程序，或者說基于回溯法的思想，這個規律可以簡單總結成：
- 固定第一個字符，遞回取得首位后面的各種字串組
- 再把第一個字符與后面每一個字符交換，并同樣遞回獲得首位后面的字串組合
- 遞回的出口，就是只剩一個字符的時候，遞回的回圈程序，就是從每個子串的第二個字符開始依次與第一個字符交換，然后繼續處理子串
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<>();
if(str != null && str.length() > 0) {
PermutationHelper(list, str.toCharArray(), 0);
Collections.sort(list);
}
return list;
}
public void PermutationHelper(ArrayList<String> list, char[] characters, int i) {
// 如果只剩一個字符，則比較結果集中是否已存在當前組合，沒有就添加
if(i == characters.length - 1) {
String str = new String(characters);
if(!list.contains(str)) {
list.add(str);
}
} else {
// 遞回的主體，第一次交換相當于固定字符，之后還要交換回來
for(int j = i; j < characters.length; j++) {
swap(characters, i, j);
PermutationHelper(list, characters, i + 1);
swap(characters, i, j);
}
}
}
public void swap(char[] characters, int i, int j) {
char temp = characters[i];
characters[i] = characters[j];
characters[j] = temp;
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/168064.html
標籤：其他