目录

牛客_JZ38字符串的排列_DFS

题目解析

C++代码

Java代码

---

牛客_JZ38字符串的排列_DFS

字符串的排列_牛客题霸_牛客网

描述：

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10
要求：空间复杂度 O(n!)，时间复杂度 O(n!)

输入描述：

输入一个字符串,长度不超过10,字符只包括大小写字母。

---

题目解析

        这是一个典型的排列问题，形如“给定一组数据，求这些数据所有的排列情况”，在这里一组数据就是字符串的字符。字符串的排列情况就是，每次需要选择一个字符（不能重复选择），按照顺序将选择的字符连接起来。

        针对排列问题，就是做选择的过程，我们需要进行n次选择，每次需要记录选择的数据且不能重复选择，具体过程如下：

1. 遍历字符串中的字符，选择一个下标未加入过的字符（因为有重复不能比较字符值）加入记录中；
2. 重复1过程，直到字符串中的字符都加入到了记录中；
3. 撤销上一次的选择，选择上一次选择的下一个字符，并重复1,2；
4. 直到上一次选择的下一个字符为空，选择过程结束。

---

C++代码

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可** * @param str string字符串 * @return string字符串vector*/vector<string> ret;string path;bool vis[11] = { false };string s;int n;vector<string> Permutation(string str) {  // Day33_3_全排列// vector<string> ret;// sort(str.begin(), str.end());// do// {//     ret.push_back(str);// }while (next_permutation(str.begin(), str.end()));// return ret;sort(str.begin(), str.end());s = str;n = s.size();dfs(0);return ret;}void dfs(int pos){if(pos == n){ret.push_back(path);return;}for(int i = 0; i < n; ++i){if(vis[i] || (i > 0 && s[i] == s[i - 1] && !vis[i - 1]))continue;path += s[i];vis[i] = true;dfs(pos + 1);vis[i] = false;path.pop_back();}}
};

Java代码

import java.util.*;
public class Solution
{boolean[] vis = new boolean[15]; // 标记当前位置是否已经使⽤过StringBuffer path = new StringBuffer();ArrayList<String> ret = new ArrayList<>(); // 收集叶⼦结点char[] s;int n;public ArrayList<String> Permutation (String str) {n = str.length();s = str.toCharArray();Arrays.sort(s);dfs(0);return ret;}public void dfs(int pos) // 填哪个位置{if(pos == n) // 收集结果{ret.add(path.toString());return;}// 填 pos 位置for(int i = 0; i < n; i++){if(vis[i])continue;if(i > 0 && s[i] == s[i - 1] && !vis[i - 1])continue;path.append(s[i]);vis[i] = true;dfs(pos + 1);// 恢复现场vis[i] = false;path.deleteCharAt(path.length() - 1);}}
}