剑指offer系列20：字符串的排列

求一个字符串中所有出现的字符的排列组合。首先把这个问题分解成若干个小问题：分治法。将所有的字符的排列可以拆分为第一个字符的选取和其余所有字符。然后其余的字符又可以拆分为第一个字符的变化选取和其余的字符串。以此类推即可得到解答。这就是很明显的递归了。注意递归的结束条件以及什么时候把这个字符串压入vector中。

 1 #include <iostream>
 2 #include <string>
 3 #include <vector>
 4 #include <algorithm>
 5 using namespace std;
 6 
 7 class Solution {
 8 private:
 9     vector<string> re;
10 public:
11     vector<string> Permutation(string str) {
12         re.clear();                //我也不知道为什么要清空
13         if (str.empty() == true)
14             return re;
15         auxi(str, 0);
16         sort(re.begin(), re.end());
17         return re;
18 
19     }
20     void auxi(string st, int begin)
21     {
22         if (st[begin] == '')//递归结束条件
23             //return;
24             re.push_back(st);
25         else {
26             for (int i = begin; st[i] != ''; i++)
27             {
28                 if (!equal(st, begin, i))
29                 {
30                     swap(st[i], st[begin]);
31                     //re.push_back(st);
32                     auxi(st, begin + 1);
33                     //swap(st[i], st[begin]);
34                 }
35 
36             }
37         }
38 
39     }
40     bool equal(string s, int a, int b)//如果前面换过了就不用再换了
41     {
42         for (int k = a; k < b; k++)
43             if (s[k] == s[b])
44                 return true;
45         return false;
46     }
47 };
48 int main()
49 {
50 
51     Solution so;
52     vector<string> cur;
53     cur = so.Permutation("abc");
54     for (int i = 0; i < cur.size(); i++)
55     {
56         cout << cur[i] << endl;
57     }
58 
59     return 0;
60 }