目錄
1.前言
2.題目解析
3.算法原理
4.代碼實現
1.前言
????????在編程練習中，字符串的全排列問題是一個經典的算法問題。通過對字符串進行全排列，可以得到該字符串的所有可能的排列組合。本文將探討如何對含有重復字符的字符串進行全排列，并且解決重復元素導致的問題。
2.題目解析
????????題目要求實現一個字符串排序的算法，即對輸入的字符串進行全排列，并返回所有可能的排列組合。需要考慮輸入字符串中存在重復字符的情況，確保不會出現重復的排列。
3.算法原理
????????針對含有重復字符的字符串進行全排列，需要使用深度優先搜索（DFS）算法結合剪枝操作來解決。在深度優先搜索過程中，需要對重復元素進行剪枝，以確保得到的排列不會包含重復的結果。
4.代碼實現
package study2.day33;import java.util.ArrayList;
import java.util.Arrays;/*** @Description: 字符串排序 就是求全排列* 錯誤原因不知道有重復字符應該怎么處理* 解決分析：排序 + dfs 填空 相同樹剪枝 a___ a___ 相同需要剪枝 (aabc的全排列)* 就是含有相同元素的全排列* @Author: windStop* @Date: 2024/5/23 14:29*/
public class Test3 {StringBuilder sb = new StringBuilder();ArrayList<String> result = new ArrayList<>();private boolean[] cheak;//判斷是否已經枚舉過了public ArrayList<String> Permutation (String str) {char[] chs = str.toCharArray();Arrays.sort(chs);cheak = new boolean[chs.length];dfs(chs);return result;}private void dfs(char[] chs) {int n = chs.length;if (sb.length() == n){result.add(sb.toString());sb = new StringBuilder();return;}for (int i = 0; i < n; i++) {if (!cheak[i]){if (i >= 1 && chs[i] == chs[i - 1] && !cheak[i - 1]) continue;//相同位置的相同元素(相同樹剪枝)sb.append(chs[i]);cheak[i] = true;dfs(chs);//遞歸完畢，進行回溯的時候說明已經是搞完了再往上返回//恢復現場cheak[i] = false;sb.delete(i,i + 1);}}}
}
)
