AlgoPressAppearance
38-字符串的排列
题目描述
https://leetcode.cn/problems/zi-fu-chuan-de-pai-lie-lcof
输入一个字符串，打印出该字符串中字符的所有排列。 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
思路：回溯法
全排列, 回溯法 使用 dfs 遍历所有元素索引，将循环结果去重加入 list
代码1，会超时
csharp
public class Solution {
List<int> arrIndex;
List<string> result;
private void dfs(char[] arr){
if(arrIndex.Count == arr.Length){
//循环结束
string str = "";
for(int i=0;i<arrIndex.Count;i++){
str+=arr[arrIndex[i]];
}
//取出重复元素
if(!result.Contains(str)){
result.Add(str);
}
}
for(int i=0; i<arr.Length; i++){
if(!arrIndex.Contains(i)){
arrIndex.Add(i);
dfs(arr);
arrIndex.Remove(i);
}
}
}
public string[] Permutation(string s) {
arrIndex = new List<int>();
result = new List<string>();
dfs(s.ToCharArray());
return result.ToArray();
}
}
代码2，使用visited 数组优化比较，直接拼凑字符串：还是超时
测试用例："dkjphedy"
csharp
public class Solution {
List<string> result;
private int[] visited;
private void dfs(string s, string str){
if(s.Length == str.Length){
//取出重复元素
if(!result.Contains(str)){
result.Add(str);
}
}
for(int i=0; i<s.Length; i++){
if(visited[i] == 0){
str+=s[i];
visited[i] = 1;
dfs(s,str);
str=str.Substring(0,str.Length-1);
visited[i] = 0;
}
}
}
public string[] Permutation(string s) {
visited = new int[s.Length];
result = new List<string>();
dfs(s,"");
return result.ToArray();
}
}
代码3，最终版：使用 visited 数组，然后排序原字符串数组去掉重复的数组，加速执行
csharp
public class Solution {
List<string> result;
private int[] visited;
private void dfs(char[] s, StringBuilder str){
if(s.Length == str.Length){
//取出元素：因为回溯的时候，去掉了重复的内容，所以此处可以直接添加
result.Add(str.ToString());
}
for(int i=0; i<s.Length; i++){
if(visited[i] == 1 || ( i > 0 && s[i] == s[i-1] && visited[i-1] == 1) ){
continue;
}
str.Append(s[i]);
visited[i] = 1;
dfs(s,str);
str.Length--;
visited[i] = 0;
}
}
public string[] Permutation(string s) {
//排序去重，减少时间执行
char[] arr = s.ToArray();
Array.Sort(arr);
visited = new int[s.Length];
result = new List<string>();
StringBuilder str = new StringBuilder();
dfs(arr,str);
return result.ToArray();
}
}
复习：20220508
csharp
public class Solution {
private List<string> result;
private List<char> list;
private bool[] visited;
private void dfs(char[] s, int index){
if(index == s.Length){
result.Add(new string(list.ToArray()));
return;
}
for(int i=0; i<s.Length; i++){
//取出重复
if(visited[i] || i > 0 && visited[i-1] && s[i] == s[i-1]){
continue;
}
list.Add(s[i]);
visited[i] = true;
dfs(s,index+1);
visited[i] = false;
list.RemoveAt(list.Count-1);
}
}
public string[] Permutation(string s) {
list = new List<char>();
result = new List<string>();
visited = new bool[s.Length];
char[] arr = s.ToArray();
Array.Sort(arr);
dfs(arr,0);
return result.ToArray();
}
}
复习去重 : 20220611
去重逻辑 strs[i] == strs[i-1] ，比如 当 aab 的时候， 加入了第一个a，dfs的时候，第二个a就不会加入。 所以第一次递归完 是 ab 结束， 当第二个从第二个 a dfs的时候，就会 第一层【第二个】a, 第二层【第一个】a，然后b，组成符合条件输出。 总结下来就是，从后面往前推算的相同字符才算，否则都不算这样只有一个结果。
csharp
public class Solution {
private List<string> list = new List<string>();
private void dfs(char[] strs, int index, StringBuilder sb, bool[] used){
if(index == strs.Length){ //输出
list.Add(sb.ToString());
return;
}
for(int i=0; i<strs.Length; i++){
if(!used[i]){
if(i>0 && used[i-1] && strs[i] == strs[i-1]){
continue;
}
sb.Append(strs[i].ToString());
used[i] = true;
dfs(strs,index+1,sb, used);
sb.Length--;
used[i] = false;
}
}
}
public string[] Permutation(string s) {
StringBuilder sb = new StringBuilder();
bool[] used = new bool[s.Length];
char[] strs = s.ToArray();
Array.Sort(strs);
dfs(strs,0,sb,used);
return list.ToArray();
}
}