剑指 Offer 38. 字符串的排列

题目

原题传送门

题解

解题思路

dfs 正常搜索就行了。
排序的话例如。用数字模拟代表字符。排序后结果为。
1 2 2 2 3
当我没有选择第一 2 数字时，第二次出现 2 我也不能进行选择。不然的话。
情况一
假设我选择1 然后选择第1个2 目前得到的序列是。
1 2 。。。
情况二
假设我选择1 然后选择第2个2 目前得到的序列是。
1 2 。。。
这样的话情况一和情况二会生成相同的排列情况。
如果我要求 如果上一个值和当前值相同，并且是没有选择的，那么当前值也不应该选择。（去除重复的策略）
那么在这种情况下。
如果我第一次出现的2 没有选择，
那么下一次就应该应该判断的3 是否选择,而不应该继续往下判断后面的 2 是否选择。
情况三 如果选择3的话，这样就不会造成重复。
1 3 。。。

代码

class Solution {
public:
    string tmp;
    void dfs(vector<string> & ans, string & s, vector<bool> flag) {
        if (s.size() == tmp.size()) {
            ans.push_back(tmp);
            return;
        }
        for (int i = 0; i < s.size(); i ++ ) {
            // 去除重复的情况。 如果上一个值和当前值相同，但是没有选择，那么当前值也不应该选择。
            if (i > 0 && !flag[i - 1] && s[i - 1] == s[i]) continue; 
            // 正常情况。
            if (!flag[i]) {
                string t = tmp;
                tmp += s[i];
                flag[i] = true;
                dfs(ans, s, flag);
                // 恢复现场。
                flag[i] = false;
                tmp = t;
            }
        }
    }
    vector<string> permutation(string s) {
        if (!s.size()) return {};
        vector<string> ans;
        // 排序便于去除重复。
        sort(s.begin(), s.end());

        vector<bool> flag(s.size(), false);
        dfs(ans, s, flag);
        return ans;
    }
};