剑指 Offer 38. 字符串的排列
本问题对应的 leetcode 原文链接：剑指 Offer 38. 字符串的排列
问题描述
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
List<Character> path;
List<String> res;
boolean[] visited;
public String[] permutation(String s) {
this.path = new ArrayList<>();
this.res = new ArrayList<>();
this.visited = new boolean[s.length()];
char[] arr = s.toCharArray();
Arrays.sort(arr);
dfs(arr, 0);
String[] ss = new String[res.size()];
for(int i = 0; i < res.size(); i++){
ss[i] = res.get(i);
}
return ss;
}
// 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
void dfs(char[] arr, int k){
if(arr.length == k){
res.add(listToString(path));
return;
}
//进行N叉树搜索
for(int i = 0; i < arr.length; i++){
// 剪枝 aab
if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
continue;
}
if(visited[i] == false){
// 递归访问
visited[i] = true;
path.add(arr[i]);
dfs(arr, k + 1);
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
String listToString(List<Character> list){
StringBuilder b = new StringBuilder();
for(int i = 0; i < list.size(); i++){
b.append(list.get(i));
}
return b.toString();
}
}
时间复杂度：O(n!n)
空间复杂度：O(n^2)
Python
class Solution(object):
def permutation(self, s):
"""
:type s: str
:rtype: List[str]
"""
path = []
res = []
visited = [False] * len(s)
arr = sorted(list(s))
def dfs(k):
if k == len(arr):
res.append("".join(path))
return
for i in range(len(arr)):
if i > 0 and arr[i] == arr[i - 1] and not visited[i - 1]:
continue
if not visited[i]:
visited[i] = True
path.append(arr[i])
dfs(k + 1)
path.pop()
visited[i] = False
dfs(0)
return res
C++
class Solution {
public:
vector<string> permutation(string s) {
vector<char> path;
vector<string> res;
vector<bool> visited(s.size(), false);
sort(s.begin(), s.end());
function<void(int)> dfs = [&](int k) {
if (k == s.size()) {
res.push_back(string(path.begin(), path.end()));
return;
}
for (int i = 0; i < s.size(); i++) {
if (i > 0 && s[i] == s[i - 1] && !visited[i - 1]) {
continue;
}
if (!visited[i]) {
visited[i] = true;
path.push_back(s[i]);
dfs(k + 1);
path.pop_back();
visited[i] = false;
}
}
};
dfs(0);
return res;
}
};
Go
func permutation(s string) []string {
var path []rune
var res []string
visited := make([]bool, len(s))
runes := []rune(s)
sort.Slice(runes, func(i, j int) bool {return runes[i] < runes[j]})
var dfs func(int)
dfs = func(k int) {
if k == len(runes) {
res = append(res, string(path))
return
}
for i := 0; i < len(runes); i++ {
if i > 0 && runes[i] == runes[i-1] && !visited[i-1] {
continue
}
if !visited[i] {
visited[i] = true
path = append(path, runes[i])
dfs(k+1)
path = path[:len(path)-1]
visited[i] = false
}
}
}
dfs(0)
return res
}
JS
/**
* @param {string} s
* @return {string[]}
*/
var permutation = function(s) {
var path = [];
var res = [];
var visited = new Array(s.length).fill(false);
var arr = s.split("");
arr.sort();
dfs(arr, 0);
var ss = new Array(res.length);
for (var i = 0; i < res.length; i++) {
ss[i] = res[i];
}
return ss;
function dfs(arr, k) {
if (arr.length === k) {
res.push(listToString(path));
return;
}
for (var i = 0; i < arr.length; i++) {
if (i > 0 && arr[i] === arr[i - 1] && visited[i - 1] === false) {
continue;
}
if (visited[i] === false) {
visited[i] = true;
path.push(arr[i]);
dfs(arr, k + 1);
path.pop();
visited[i] = false;
}
}
}
function listToString(list) {
var b = "";
for (var i = 0; i < list.length; i++) {
b += list[i];
}
return b;
}
};