题解 | #字符串的排列#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param str string字符串 
     * @return string字符串vector
     */
    vector<string> ans;  // 方案
    string path;  // 位置
    vector<bool> st;  // 标记是否用过
    vector<string> Permutation(string str) {
        // write code here
        sort(str.begin(), str.end());  // 排序
        st = vector<bool>(str.size());  // 初始长度
        dfs(str);
        return ans;
    }

    void dfs(string &str) {
        if (str.length() == path.length()) {  // path表示位置如果枚举完所有位置，说明当前就是一个方案
            ans.push_back(path);
            return;
        }
        for (int i = 0;  i < str.length(); i ++ ) {
            if (!st[i]) {  // 如果这个位置没有用过我们就可以填入
                if (i > 0 && str[i - 1] == str[i] && !st[i - 1]) continue;  // 如果前一个字符等于当前字符 并且 前面的位置没有被用过就跳过
                path.push_back(str[i]);  // 插入第i个字符

                st[i] = true;  // 标记已用过
                dfs(str);  // 递归到下一层
                st[i] = false;  // 恢复现场
                path.pop_back();  // 恢复现场

            }
        }
    }
};