Cinte's Leetcode Record
0%

面试题 08.07. 无重复字符串的排列组合

Posted on Edited on In Disqus:
Symbols count in article: 993 Reading time ≈ 1 mins.

面试题 08.07. 无重复字符串的排列组合

BackTrack
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
28
29
class Solution {
public:
    vector<string> permutation(string S) {
        vector<string> ret;
        string tmp;
        vector<int> visited(S.size());
        backTrack(ret, S, tmp, visited);
        return ret;
    }
private:
    void backTrack(vector<string>& ret, string& S, string& tmp, vector<int>& visited)
    {
        if(tmp.size() == S.size())
        {
            ret.push_back(tmp);
            return;
        }
        for(int i = 0; i < S.size(); ++i)
        {
            if(visited[i])
                continue;
            tmp += S[i];
            visited[i] = 1;
            backTrack(ret, S, tmp, visited);
            tmp.pop_back();
            visited[i] = 0;
        }
    }
};

一种基于交换的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<string> permutation(string S) {
        helper(S, 0, S.size());
        return vector<string>(ret.begin(), ret.end());
    }
private:
    unordered_set<string> ret;
    void helper(string& S, int start, int n)
    {
        for(int i = start; i < n; ++i)
        {
            swap(S[start], S[i]);
            ret.insert(S);
            helper(S, start + 1, n);
            swap(S[start], S[i]);
        }
    }
};