返回全排列，力扣38.字符串的排列

时隔好久，又捡起了力扣，开始刷题，争取年前，把剑指offer刷完。

力扣38，是要求出字符串的全排列，高中的时候学过排列与组合，因此可以迅速的推出所有的组合数为s!;

我们可以采用DFS的方法，首先确定第一位，然后确定第二位，最终确定第n位，然后返回最终的结果；为了去除重复字符，可以利用一个unordered_set存储字符串，做一个“剪枝”操作。

class Solution {
   
public:
    vector<string> permutation(string s) {
   
        //DFS结合HashSet
        //固定一位字符，然后固定下一位字符，直到最后的一位，然后返回最终的字符串
        //时间复杂度：O(N!);空间复杂度：O(N^2)
        dfs(s,0);
        return Res;
    }
private:
    vector<string> Res;
    void dfs(string &s,int x){
   
        //调用一次就可以自动将所有的排列保存到字符数组Res里面
        if(x==s.length()-1){
   
            Res.push_back(s);
            return;
        }
        unordered_set<int> st;
        for(int i=x;i<s.length();++i){
   
            if(st.find(s[i])!=st.end())
                continue; //字符重复，“剪枝”
            st.insert(s[i]);
            swap(s[i],s[x]);//固定第x位
            dfs(s,x+1);
            swap(s[i],s[x]);
        }

    }
};

题外话：

1. set与unordered_set的区别?
   unordered_set的实现基于哈希表，因此不是顺序存储，set是基于红黑树实现的
2. count() 与find() 的区别?
   count()返回0或1，找到了返回1，否则返回0；
   find()返回iterator，找到了返回对应的iterator，否则返回end();