题解 | #字符串的排列#

方法：BFS（深度优先搜索）

此题与有重复项数字的全排列相同，不再详细解答。

时间复杂度：o(n*n!)

空间复杂度：o(n)

class Solution {
  public:
    vector<string> Permutation(string str) {
        //特殊情况处理（空字符串）
        if (str.size() == 0)
            return res;

        //按字典序排序
        sort(str.begin(), str.end());
        vector<bool> flag(str.size(), false);
        resort(flag, str, 0);
        return res;
    }

  private:
    vector<string> res;
    string temp;

    void resort(vector<bool>& flag, string& str, int idx) {
        if (idx == str.size()) {
            res.push_back(temp);
        } else {
            for (int i = 0; i < str.size(); i++) {
                if (flag[i] == false) {
                    //去除重复的数字
                    if (i > 0 && str[i - 1] == str[i] && flag[i - 1] == false)
                        continue;
                    temp.push_back(str[i]);
                    flag[i] = true;
                    resort(flag, str, idx + 1);
                    //回溯
                    temp.pop_back();
                    flag[i] = false;
                }
            }
        }
    }
};