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

题面

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

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

示例

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

限制

11 <= s 的长度 <= 8

思路

dfs遍历回溯。

代码

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