38. 字符串的排列【难】

---

comments: true
difficulty: 中等
edit_url: https://github.com/doocs/leetcode/edit/main/lcof/%E9%9D%A2%E8%AF%95%E9%A2%9838.%20%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%9A%84%E6%8E%92%E5%88%97/README.md

面试题 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]

 

限制：

1 <= s 的长度 <= 8

解法

方法一：回溯 + 哈希表

我们设计一个函数 $dfs(i)$，表示当前排列到了第 $i$ 个位置，我们需要在第 $i$ 个位置上填入一个字符，这个字符可以从 $s[i..n-1]$ 中任意选择。

函数 $dfs(i)$ 的执行过程如下：

• 如果 $i=n-1$，说明当前排列已经填满，将当前排列加入答案，返回。
• 否则，我们需要在 $s[i..n-1]$ 中选择一个字符填入第 $i$ 个位置，我们可以使用哈希表记录哪些字符已经被填过，从而避免重复填入相同的字符。
• 在 $s[i..n-1]$ 中选择一个字符填入第 $i$ 个位置，然后递归执行函数 $dfs(i+1)$，即填入第 $i+1$ 个位置。
• 回溯，撤销选择，即将第 $i$ 个位置的字符填回原位。

我们在主函数中调用函数 $dfs(0)$，即从第 0 个位置开始填入字符。最后返回答案数组即可。

时间复杂度 $O(n!\times n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。需要进行 $n!$ 次排列，每次排列需要 $O(n)$ 的时间复制字符串。

【LeetCode刷题力扣题解 | 剑指Offer 38. 字符串的排列 | 思路讲解及Python3代码实现】 https://www.bilibili.com/video/BV1cK4y1s7tN/?share_source=copy_web&vd_source=ed4a51d52f6e5c9a2cb7def6fa64ad6a

Python3

class Solution:def permutation(self, s: str) -> List[str]:def dfs(i):if i == len(s) - 1:ans.append(''.join(cs))returnvis = set()for j in range(i, len(s)):if cs[j] not in vis: #3)"同层剪枝"vis.add(cs[j]) #2)利用set完成交换过程中的去重cs[i], cs[j] = cs[j], cs[i] #1)利用交换完成排序：从首位开始，分别将位置j∈(i,len(s)] 和 位置交换 构建多个分支dfs(i + 1)cs[i], cs[j] = cs[j], cs[i]ans = []cs = list(s)dfs(0)return ans

Java

class Solution {private List<String> ans = new ArrayList<>();private char[] cs;public String[] permutation(String s) {cs = s.toCharArray();dfs(0);return ans.toArray(new String[ans.size()]);}private void dfs(int i) {if (i == cs.length - 1) {ans.add(String.valueOf(cs));return;}Set<Character> vis = new HashSet<>();for (int j = i; j < cs.length; ++j) {if (vis.add(cs[j])) {swap(i, j);dfs(i + 1);swap(i, j);}}}private void swap(int i, int j) {char t = cs[i];cs[i] = cs[j];cs[j] = t;}
}

C++

class Solution {
public:vector<string> permutation(string s) {vector<string> ans;function<void(int)> dfs = [&](int i) {if (i == s.size() - 1) {ans.push_back(s);return;}unordered_set<char> vis;for (int j = i; j < s.size(); ++j) {if (!vis.count(s[j])) {vis.insert(s[j]);swap(s[i], s[j]);dfs(i + 1);swap(s[i], s[j]);}}};dfs(0);return ans;}
};

Go

func permutation(s string) (ans []string) {cs := []byte(s)var dfs func(int)dfs = func(i int) {if i == len(s)-1 {ans = append(ans, string(cs))return}vis := map[byte]bool{}for j := i; j < len(s); j++ {if !vis[cs[j]] {vis[cs[j]] = truecs[i], cs[j] = cs[j], cs[i]dfs(i + 1)cs[i], cs[j] = cs[j], cs[i]}}}dfs(0)return
}

TypeScript

function permutation(s: string): string[] {const n = s.length;const cs = s.split('');const set = new Set<string>();const dfs = (i: number) => {if (i === n) {set.add(cs.join(''));return;}dfs(i + 1);for (let j = i + 1; j < n; j++) {[cs[i], cs[j]] = [cs[j], cs[i]];dfs(i + 1);[cs[i], cs[j]] = [cs[j], cs[i]];}};dfs(0);return [...set];
}

Rust

use std::collections::HashSet;
impl Solution {fn dfs(i: usize, cs: &mut Vec<char>, res: &mut Vec<String>) {if i == cs.len() {res.push(cs.iter().collect());return;}let mut set = HashSet::new();for j in i..cs.len() {if set.contains(&cs[j]) {continue;}set.insert(cs[j]);cs.swap(i, j);Self::dfs(i + 1, cs, res);cs.swap(i, j);}}pub fn permutation(s: String) -> Vec<String> {let mut res = Vec::new();Self::dfs(0, &mut s.chars().collect(), &mut res);res}
}

JavaScript

/*** @param {string} s* @return {string[]}*/
var permutation = function (s) {const cs = s.split('');const ans = [];const n = s.length;const dfs = i => {if (i == n - 1) {ans.push(cs.join(''));return;}const vis = new Set();for (let j = i; j < n; ++j) {if (!vis.has(cs[j])) {vis.add(cs[j]);[cs[i], cs[j]] = [cs[j], cs[i]];dfs(i + 1);[cs[i], cs[j]] = [cs[j], cs[i]];}}};dfs(0);return ans;
};

C#

public class Solution {private char[] cs;private List<string> ans = new List<string>();public string[] Permutation(string s) {cs = s.ToCharArray();dfs(0);return ans.ToArray();}private void dfs(int i) {if (i == cs.Length - 1) {ans.Add(new string(cs));return;}var vis = new HashSet<char>();for (int j = i; j < cs.Length; ++j) {if (vis.Add(cs[j])) {(cs[i], cs[j]) = (cs[j], cs[i]);dfs(i + 1);(cs[i], cs[j]) = (cs[j], cs[i]);}}}
}

Swift

class Solution {private var ans: [String] = []private var cs: [Character] = []func permutation(_ s: String) -> [String] {cs = Array(s)dfs(0)return ans}private func dfs(_ i: Int) {if i == cs.count - 1 {ans.append(String(cs))return}var vis: Set<Character> = []for j in i..<cs.count {if !vis.contains(cs[j]) {vis.insert(cs[j])swap(i, j)dfs(i + 1)swap(i, j)}}}private func swap(_ i: Int, _ j: Int) {let t = cs[i]cs[i] = cs[j]cs[j] = t}
}