C++刷剑指offer(面试题38. 字符串的排列)【高频】

糖逗

题目描述：

1. 输入一个字符串，打印出该字符串中字符的所有排列。
   
2. 
   
3.  
   
4. 
   
5. 你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
   
6. 
   
7.  
   
8. 
   
9. 示例:
   
10. 
    
11. 输入：s = "abc"
    
12. 输出：["abc","acb","bac","bca","cab","cba"]
    
13.  
    
14. 
    
15. 限制：
    
16. 
    
17. 1 <= s 的长度 <= 8
    
18. 
    
19. 来源：力扣（LeetCode）
    
20. 链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
    
21. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include <iostream>
   
2. #include <string>
   
3. #include <vector>
   
4. #include <set>
   
5. 
   
6. using namespace std;
   
7. 
   
8. void solution(string& input, vector<bool>& visit, set<string>& res, string& temp, int index){
   
9.         if(index == input.size()) res.insert(temp);
   
10.         for(int i = 0; i < input.size(); i++){
    
11.                 if(!visit[i]){
    
12.                         temp.push_back(input[i]);
    
13.                         visit[i] = true;
    
14.                         solution(input, visit, res, temp, index+1);
    
15.                         temp.erase(temp.end()-1);
    
16.                         visit[i] = false;
    
17.                 }               
    
18.         }
    
19. }
    
20. 
    
21. 
    
22. vector<string> permutation(string input) {
    
23.     set<string> res;
    
24.         string temp;
    
25.         int index = 0;
    
26.         vector<bool> visit;
    
27.         visit.resize(input.size(), false);
    
28.        
    
29.         solution(input, visit, res, temp, index);
    
30.     return vector<string>(res.begin(), res.end());
    
31. }
    
32. 
    
33. 
    
34. int main(void){
    
35.         string input;
    
36.         cin >> input;
    
37.        
    
38.         vector<string> result = permutation(input);
    
39.        
    
40.         for(int i= 0; i < result.size(); i++){
    
41.                 cout << "------------" << endl;
    
42.                 cout << result[i] << endl;
    
43.         }
    
44. 
    
45.        
    
46.         return 0;
    
47. }

复制代码

注意事项：
1.回溯思想，一般能把问题化成树分支的问题可以试试回溯，回溯涉及到剪枝。
2.参考链接：https://blog.csdn.net/qq_43152052/article/details/104464542
3.参考视频链接：https://www.bilibili.com/video/B ... 6093610650574172674
4.代码的思路图如图1

糖逗

糖逗

相似题型：面试题 08.12. 八皇后

1. 设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。
   
2. 
   
3. 注意：本题相对原题做了扩展
   
4. 
   
5. 示例:
   
6. 
   
7. 输入：4
   
8. 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
   
9. 解释: 4 皇后问题存在如下两个不同的解法。
   
10. [
    
11. &#160;[".Q..", &#160;// 解法 1
    
12. &#160; "...Q",
    
13. &#160; "Q...",
    
14. &#160; "..Q."],
    
15. 
    
16. &#160;["..Q.", &#160;// 解法 2
    
17. &#160; "Q...",
    
18. &#160; "...Q",
    
19. &#160; ".Q.."]
    
20. ]
    
21. 
    
22. 来源：力扣（LeetCode）
    
23. 链接：https://leetcode-cn.com/problems/eight-queens-lcci
    
24. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. #include<string>
   
2. #include<vector>
   
3. #include<iostream>
   
4. 
   
5. using namespace std;
   
6. 
   
7. bool valid(vector<int>& pos, int x, int y){
   
8.         for(int i = 0; i < pos.size(); i++){
   
9.                 if(i == x || y == pos[i] || x + y == i + pos[i] || x + pos[i] == y + i)return false;
   
10.                
    
11.         }
    
12.         return true;
    
13. }
    
14. 
    
15. 
    
16. 
    
17. void dfs(int n, int x, vector<int>& pos, vector<string>& temp, vector<vector<string> >& res){
    
18.         if(x == n) res.push_back(temp);
    
19.         for(int y= 0 ; y < n; y ++){
    
20.                 if(valid(pos, x, y)){
    
21.                         temp[x][y] = 'Q';
    
22.                         pos.push_back(y);
    
23.                         dfs(n, x+1, pos, temp, res);
    
24.                         pos.pop_back();
    
25.                         temp[x][y] = '.';
    
26.                 }       
    
27.         }
    
28. }
    
29. 
    
30. 
    
31. 
    
32. vector<vector<string> > solution(int n){
    
33.         vector<vector<string> > res;
    
34.         vector<string>temp (n, string(n, '.'));
    
35.         vector<int> pos;
    
36.         dfs(n, 0, pos, temp, res);
    
37.         return res;
    
38. }
    
39. 
    
40. 
    
41. 
    
42. 
    
43. int main(void){
    
44.         int n;
    
45.         cin >> n;
    
46.         vector<vector<string> > res = solution(n);
    
47.         for(int i = 0; i < res.size(); i++){
    
48.                 for(int j = 0; j < res[i].size(); j++){
    
49.                         cout << res[i][j] <<  endl;
    
50.                 }
    
51.                 cout << endl;
    
52.                 cout << "------------------" << endl;
    
53.         }
    
54.         return 0;
    
55. }
    

复制代码

参考链接：
1.x + y == i + pos[i] || x + pos[i] == y + i  可参见链接：https://leetcode-cn.com/problems ... u-zu-ji-lu-dui-jia/