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"));
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/539613.html
標籤：其他
上一篇：進位制數的靈活運用