剑指offer38 字符串的排列

思路：

递归+回溯，关键是去重。

实现1（在原字符串中通过交换的方式生成排列）：

 1 class Solution
 2 {
 3 public:
 4     void dfs(string &s, int p, vector<string>& res)
 5     {
 6         int n = s.length();
 7         if (p == n - 1) { res.push_back(s); return; }
 8         vector<bool> vis(26, false);
 9         for (int i = p; i < n; i++)
10         {
11             int tmp = s[i] - 'a';
12             if (vis[tmp]) continue;
13             vis[tmp] = true;
14             swap(s[p], s[i]);
15             dfs(s, p + 1, res);
16             swap(s[p], s[i]);
17         }
18     }
19     vector<string> permutation(string s)
20     {
21         vector<string> res;
22         dfs(s, 0, res);
23         return res;
24     }
25 };

实现2（开辟新的缓冲区，不断选取未使用过的字符追加到缓冲区末尾生成排列）：

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