[数据结构与算法]LeetCode--字符串的排列

思路来源：传送门

题目给的字符串是有重复字符的
一开始自己做的是最后用vector去重的
sort(vec.begin(), vec.end());
vec.erase(unique(vec.begin(), vec.end()), vec.end());
但是感觉这样的话没什么难度

然后看了别人的思路，学到了不少
①首先通过在原有字符串上交换元素得到不同的排列，首先固定第一个位置，然后固定第二个位置，以此类推…
②怎么做到的去重呢？比如字符串是这样baac，我们把第一个a放到索引0位置上，后面剩余的元素是bac；把第二个a放在索引0位置上，剩余的元素是abc。剩余的元素一样，经过多次排列后，结果肯定也一样，所以就有了下面去重位置的代码，不用把相同的元素放在同样的位置上

class Solution {
private:
    vector<string> ans;
public:
    vector<string> permutation(string s) {
        dfs(s, 0);
        return ans;
    }

    void dfs(string& s, int pos) {
        if (pos == s.size() - 1) {
            ans.push_back(s);
            return;
        }
        for (int i = pos; i < s.size(); i++) {
            bool flag = true;
            for (int j = pos; j < i; j++) { //去重
                if (s[j] == s[i])
                    flag = false;
            }
            if (flag) {
                swap(s[i], s[pos]);
                dfs(s, pos + 1);
                swap(s[i], s[pos]);
            }
        }
    }
};