剑指 Offer 38. 字符串的排列

剑指 Offer 38. 字符串的排列

难度：$middle$

题目描述

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

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

示例:

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

限制：

$1<=s的长度<=8$

算法

(dfs)

递归解析：

终止条件： 当 x = len(s) - 1 时，代表所有位已固定（最后一位只有 1 种情况），则将当前组合 s 转化为字符串并加入 res ，并返回；

递推参数： 当前固定位 x ；

递推工作： 初始化一个 Set ，用于排除重复的字符；将第 x 位字符与 i ∈ [x, len©] 字符分别交换，并进入下层递归；

• 剪枝： 若 c[i] 在 Set​ 中，代表其是重复字符，因此 “剪枝” ；
• 将 c[i] 加入 Set​ ，以便之后遇到重复字符时剪枝；
• 固定字符： 将字符 c[i] 和 c[x] 交换，即固定 c[i] 为当前位字符；
• 开启下层递归： 调用 dfs(x + 1) ，即开始固定第 x + 1 个字符；
• 还原交换： 将字符 c[i] 和 c[x] 交换（还原之前的交换）；

C++ 代码

class Solution {
public:vector<string> permutation(string s) {dfs(s, 0);return res;}vector<string> res;void dfs(string s, int x){if (x == s.size() - 1){res.push_back(s);return;}set<int> st;for (int i = x; i < s.size(); i ++){if (st.find(s[i]) != st.end()) continue;st.insert(s[i]);swap(s[i], s[x]);dfs(s, x + 1);swap(s[i], s[x]);}}
};