题解 | #字符串的排列#

刚看到题其实稍微有点蒙，不过看了题目配的图就很简单了。
图里已经给出了一种解题思路。按顺序遍历遍历字符串，对每一个字符都调换它以及大于等于它的下标的字符，将新得到的字符串压栈，并对新字符串也执行该操作，直到遍历完整个字符串。
由于调用的层数比较深，这里选择递归的方法来实现。传入参数中的index为开始交换的下标。
第一次写完代码测试时，发现"aab"的调用结果会出现6个，其中有三个重复的，所以正确结果应该是3个。为了解决重复元素造成的重复结果这一问题，选择先将得到的数组变为集合，再将集合变回数组的方式解决。

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string> result;
        if(str.length() == 1){
            result.push_back(str);
            return result;
        }
        arrange(result, str, 0);
        set<string> s(result.begin(),result.end());
        vector<string> nr(s.begin(),s.end());
        return nr;
    }
    void arrange(vector<string> &result, string str, int index){
        if(index == str.length() - 1){
            return;
        }
        for(int i = index;i < str.length();i++){
            string cp = str;
            char temp = cp[index];
            cp[index] = str[i];
            cp[i] = temp;
            result.push_back(cp);
            arrange(result, cp, index + 1);
        }
    }
};