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

糖逗

题目描述：

输入一个字符串，打印出该字符串中字符的所有排列。

 

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

 

示例:

输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
 

限制：

1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include <iostream>
#include <string>
#include <vector>
#include <set>

using namespace std;

void solution(string& input, vector<bool>& visit, set<string>& res, string& temp, int index){
        if(index == input.size()) res.insert(temp);
        for(int i = 0; i < input.size(); i++){
                if(!visit[i]){
                        temp.push_back(input[i]);
                        visit[i] = true;
                        solution(input, visit, res, temp, index+1);
                        temp.erase(temp.end()-1);
                        visit[i] = false;
                }                
        }
}


vector<string> permutation(string input) {
    set<string> res;
        string temp;
        int index = 0;
        vector<bool> visit;
        visit.resize(input.size(), false);
        
        solution(input, visit, res, temp, index);
    return vector<string>(res.begin(), res.end());
}


int main(void){
        string input;
        cin >> input;
        
        vector<string> result = permutation(input);
        
        for(int i= 0; i < result.size(); i++){
                cout << "------------" << endl;
                cout << result[i] << endl;
        }

        
        return 0;
} 

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

糖逗

糖逗

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

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线。

注意：本题相对原题做了扩展

示例:

 输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/eight-queens-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

#include<string>
#include<vector>
#include<iostream>

using namespace std;

bool valid(vector<int>& pos, int x, int y){
        for(int i = 0; i < pos.size(); i++){
                if(i == x || y == pos[i] || x + y == i + pos[i] || x + pos[i] == y + i)return false;
                
        }
        return true;
}



void dfs(int n, int x, vector<int>& pos, vector<string>& temp, vector<vector<string> >& res){
        if(x == n) res.push_back(temp);
        for(int y= 0 ; y < n; y ++){
                if(valid(pos, x, y)){
                        temp[x][y] = 'Q';
                        pos.push_back(y);
                        dfs(n, x+1, pos, temp, res);
                        pos.pop_back();
                        temp[x][y] = '.';
                }        
        }
}



vector<vector<string> > solution(int n){
        vector<vector<string> > res;
        vector<string>temp (n, string(n, '.'));
        vector<int> pos;
        dfs(n, 0, pos, temp, res);
        return res;
}




int main(void){
        int n;
        cin >> n;
        vector<vector<string> > res = solution(n);
        for(int i = 0; i < res.size(); i++){
                for(int j = 0; j < res[i].size(); j++){
                        cout << res[i][j] <<  endl;
                } 
                cout << endl;
                cout << "------------------" << endl;
        }
        return 0;
}
 

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