【题解】剑指Offer-38 字符串的排列

字符串的排列(剑指Offer-38)

题面

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

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

示例

1
2
输入:s = "abc"
输出:["abc","acb","bac","bca","cab","cba"]

限制

1
1 <= s 的长度 <= 8

思路

dfs遍历回溯。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
vector<string> ans;
void dfs(string s, string &t, vector<bool> &vis){
if(s.size() == t.size()){
ans.push_back(t);
return;
}
for(int i=0; i<s.size(); i++){
if(vis[i]) continue;
if(i && s[i-1]==s[i] && !vis[i-1]) continue;
t.push_back(s[i]);
vis[i] = true;
dfs(s, t, vis);
vis[i] = false;
t.pop_back();
}
}
public:
vector<string> permutation(string s) {
if(s.size() == 0) return {};
string t = "";
sort(s.begin(), s.end());
vector<bool> vis(s.size());
dfs(s, t, vis);
return ans;
}
};