[好题!] 剑指offer 38 字符串全排列

输入一个字符串，打印出该字符串中字符的所有排列。

第一位有n种可能, 对于每一种可能下, 有n-1种排列可能....
使用cursor变量指名已经固定到第几位, 如果已经固定到最后一位, 那么证明这是一个结果, 可以push_back

要注意的问题是, 可能存在重复的字母, 因此我们需要明确: 对于每一位, 某个字母只能出现一次.
在judge()中, end是要放入cursor的变量, 从begin一直找到end-1, 看是否有相同的元素, 如果有, 证明在之前的循环中, 这个变量已经被放入过cursor中, 本次跳过.

class Solution {
public:
    vector<string> result;
    vector<string> permutation(string s) {
        check(s, 0);
        return result;
    }
    void check(string &s, int cursor)
    {
        if(cursor == s.size()-1) 
        {
            result.push_back(s);
        }
        else{
            for(int i = cursor; i<s.size(); i++)
            {

                //检查是否存在相等
                if(judge(s, cursor, i)) continue;
                swap(s[i], s[cursor]);
                check(s,cursor+1);
                swap(s[i], s[cursor]);

            }
        }

        
    }

    bool judge(string &s, int begin, int end)
    {
        for(int i = begin; i< end; i++)
        {
            if(s[i] == s[end]) return true;
        }
        return false;
    }
};