你能幫我理解下面的代碼片段嗎？注釋說它正在通過回溯進行字串排列，但我就是不明白。我不明白嵌套的 for 回圈在做什么。我試圖用“Cat”跟隨代碼。排列集沒有呢？
public static Set<String> getPermutations(String inputString) {
if(inputString.length() <= 1) {
return new HashSet<>(Collections.singletonList(inputString));
}
String allCharsExceptLast = inputString.substring(0, inputString.length()-1);
char lastChar = inputString.charAt(inputString.length()-1);
Set<String> permutationsOfAllCharsExceptLast = getPermutations(allCharsExceptLast);
Set<String> permutations = new HashSet<>();
for(String permutationOfAllCharsExceptLast: permutationsOfAllCharsExceptLast) {
for(int position = 0; position <= allCharsExceptLast.length(); position ) {
String permutation = permutationOfAllCharsExceptLast.substring(0, position) lastChar
permutationOfAllCharsExceptLast.substring(position);
permutations.add(permutation);
}
}
return permutations;
}
}
uj5u.com熱心網友回復：
該演算法的作業原理如下：
基本情況：當字串僅包含一個字符時，則回傳僅包含該字串的集合：這是唯一可能的排列。
解決少一個字符的問題：獲取缺少原始最后一個字符的較短字串的所有排列。
對于此遞回呼叫回傳的集合中的每個排列，請執行以下操作：
在這個排列中選擇每個可能的索引，我們可以在其中插入一個字符，即 0 到較短字串的長度（包括）：
- 在這個排列中，在給定的索引處：插入被排除的字符，從而構造一個現在包含所有字符的排列。
因此，第 3 步需要兩個嵌套回圈：一個用于獲取較短字串的每個排列，另一個用于選擇將排除字符插入該排列的索引。
例子：
輸入：
"abcd"
在步驟 2 中，我們查看較短的字串“abc”，并相信該函式會為其產生正確的結果（歸納推理），即集合：
{ "abc", "acb", "bac", "bca", "cab", "cba" }
現在我們進入第 3 步。外部回圈遍歷這個集合。內部回圈選擇 0 到 3 之間的索引（包括在內）。所以讓我們把它放在一個表中：
| 更短的排列 | 插入“d”的索引 | 結果排列 |
|---|---|---|
| “ABC” | 0 | “dabc” |
| “ABC” | 1 | “亞行” |
| “ABC” | 2 | “abdc” |
| “ABC” | 3 | “A B C D” |
| “acb” | 0 | “dacb” |
| “acb” | 1 | “adcb” |
| “acb” | 2 | “acdb” |
| “acb” | 3 | “acbd” |
| “背” | 0 | “資料庫” |
| “背” | 1 | “bdc” |
| “背” | 2 | “壞” |
| “背” | 3 | “背” |
| “bca” | 0 | “資料庫” |
| “bca” | 1 | “bdca” |
| “bca” | 2 | “bcda” |
| “bca” | 3 | “bcad” |
| “出租車” | 0 | “dcab” |
| “出租車” | 1 | “cdab” |
| “出租車” | 2 | “卡布” |
| “出租車” | 3 | “出租車” |
| “cba” | 0 | “dcba” |
| “cba” | 1 | “cdba” |
| “cba” | 2 | “cbda” |
| “cba” | 3 | “cbad” |
然后回傳這個結果集。
希望這可以澄清它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/caozuo/420164.html
標籤：