【一刷《剑指Offer》】面试题 28：字符串的排列

牛客对应题目链接：字符串的排列_牛客题霸_牛客网 (nowcoder.com)

力扣对应题目链接：LCR 157. 套餐内商品的排列顺序 - 力扣（LeetCode）

核心考点 ：全排列问题， DFS。

一、《剑指Offer》对应内容

二、分析题目

全排列问题，可以看做如下多叉树形态：

很明显，我们想要得到合适的排列组合，一定是深度优先的。该问题可以把目标串理解成两部分：

第一部分：以哪个字符开头。
第二部分：剩下的是子问题。

所以，我们要让每个字符都要做一遍开头，然后再求解子问题。

三、代码

//牛客
//写法一
class Solution {
private:
    set<string> ans;
    vector<string> res;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    void swap(string &str, int i, int j)
    {
        char temp=str[i];
        str[i]=str[j];
        str[j]=temp;
    }
    void dfs(string &str, int start)
    {
        if(start==str.length()-1)
        {
            ans.insert(str);
            return;
        }
        for(int i=start; i<str.size(); i++)
        {
            swap(str, start, i);
            dfs(str, start+1);
            swap(str, start, i);
        }
    }
    vector<string> Permutation(string str) {
        int n=str.size();
        if(n<1) return {""};
        dfs(str, 0);
        for(auto s : ans)
            res.push_back(s);
        return res;
    }
};

//写法二
class Solution {
private:
    set<string> ans;
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    void dfs(string &str, int pos)
    {
        if(pos==str.length()-1)
        {
            ans.insert(str);
            return;
        }
        for(int i=pos; i<str.size(); i++)
        {
            swap(str[pos], str[i]);
            dfs(str, pos+1);
            swap(str[pos], str[i]);
        }
    }
    vector<string> Permutation(string str) {
        if(str.size()<1) return {""};
        dfs(str, 0);
        return vector<string>({ans.begin(), ans.end()});
    }
};

//力扣
class Solution {
private:
    set<string> ans;
    vector<string> res;
public:
    void dfs(string& goods, int pos)
    {
        if(pos==goods.size()-1)
        {
            ans.insert(goods);
            return;
        }
        for(int i=pos; i<goods.size(); i++)
        {
            swap(goods[pos], goods[i]);
            dfs(goods, pos+1);
            swap(goods[pos], goods[i]);
        }
    }
    vector<string> goodsOrder(string goods) {
        dfs(goods, 0);
        for(auto s : ans)
            res.push_back(s);
        return res;
    }
};

四、扩展

五、相关题目

1、正方体的三面和

输入一个含有 8 个数字的数组，判断有没有可能把这 8 个数字分别放到正方体的 8 个顶点上（如图 4.15 所示），使得正方体上三组相对的面上的 4 个顶点的和都相等。

这相当于先得到 a1、a2、a3、a4、a5、a6、a7 和 a8 这 8 个数字的所有排列，然后判断有没有某一个的排列符合题目给定的条件，即 a1+a2+a3+a4==a5+a6+a7+a8，a1+a3+a5+a7==a2+a4+a6+a8，并且 a1+a2+a5+a6==a3+a4+a7+a8。

2、八皇后

在 8 X 8 的国际象棋上摆放 8 个皇后，使其不能相互攻击，即任意两个皇后不得处在同一行、同一列或者同一对角线上。图 4.16 中的每个黑色格子表示一个皇后，这就是一种符合条件的摆放方法。请问总共有多少种符合条件的摆法？

由于 8 个皇后的任意两个不能处在同一行，那么肯定是每一个皇后占据一行。于是我们可以定义一个数组 ColumnIndex[8]，数组中第 i 个数字表示位于第 i 行的皇后的列号。先把 ColumnIndex 的 8 个数字分别用 0~7 初始化，接下来就是对数组 ColumnIndex 做全排列。因为我们是不同的数字初始化数组，所以任意两个皇后肯定不同列。我们只需判断每一个排列对应的 8 个皇后是不是在同意对角线上，也就是对于数组的两个下标 i 和 j，是不是 i-j==ColumnIndex[i]-ColumnIndex[j] 或者 j-i==ColumnIndex[i]-ColumnIndex[j]。

力扣对应类似题目链接：51. N 皇后 - 力扣（LeetCode）

//写法一
class Solution {
private:
    vector<string> path;
    vector<vector<string>> res;
    vector<bool> checkCol, checkDg, checkUdg;
public:
    void dfs(int row, int n)
    {
        if(row==n)
        {
            res.push_back(path);
            return;
        }
        for(int col=0; col<n; col++)
        {
            if (!checkCol[col] && !checkDg[row-col+n] && !checkUdg[row+col])
            {
                path[row][col]='Q';
                checkCol[col]=checkDg[row-col+n]=checkUdg[row+col]=true;
                dfs(row+1, n);
                checkCol[col]=checkDg[row-col+n]=checkUdg[row+col]=false;
                path[row][col]='.';
            }
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        checkCol = vector<bool>(n, false);
        checkDg = vector<bool>(2*n, false);
        checkUdg = vector<bool>(2*n, false);
        path.resize(n);
        for(int i=0; i<n; i++)
            path[i].append(n, '.');
        dfs(0, n);
        return res;
    }
};

//写法二
class Solution {
public:
    vector<vector<string>> res;
    void dfs(int x, int n, vector<string>& chessboard)
    {
        if(x==n)
        {
            res.push_back(chessboard);
            return;
        }
        for (int y=0; y<n; y++)
        {
            if (isValid(x, y, n, chessboard))
            {
                chessboard[x][y]='Q';
                dfs(x+1, n, chessboard);
                chessboard[x][y]='.';
            }
        }
    }

    bool isValid(int x, int y, int n, vector<string>& chessboard)
    {
        // 检查列
        for (int i=0; i<x; i++)
        {
            if (chessboard[i][y]=='Q')
                return false;
        }
        // 检查 45度角是否有皇后
        for (int i=x-1, j=y-1; i>=0 && j>=0; i--, j--)
        {
            if (chessboard[i][j]=='Q')
                return false;
        }
        // 检查 135度角是否有皇后
        for(int i=x-1, j=y+1; i>=0 && j<n; i--, j++)
        {
            if (chessboard[i][j]=='Q')
                return false;
        }
        return true;
    }

    vector<vector<string>> solveNQueens(int n) {
        vector<string> chessboard(n, string(n, '.'));
        dfs(0, n, chessboard);
        return res;
    }
};