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

发表于 分类于 ， ， ， 本文字数： 89 阅读时长 ≈ 1 分钟
剑指Offer-38 字符串的排列 类型 DFS

字符串的排列(剑指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;
    }
};