题解 | #字符串的排列#

#include <algorithm>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串vector
     */
    void Permutation(vector<string> & res,string str_head, string str,vector<bool> vt_vis)
    {
        if (str_head.length() == str.length()) {
            res.push_back(str_head);
        }

        for (int i=0; i<vt_vis.size(); i++) {
            if (vt_vis[i]) {
                continue;
            }

		//多个重复的字符，因为第二个重复字符continue了
		//所以最后str_head的长度无法达标，从而淘汰了后面继续使用多个重复的结果
            if (i>0 && str[i] == str[i-1] && vt_vis[i-1]) {
                continue;
            }

            vt_vis[i] = true;
            string str_head_temp = str_head + str[i];
            Permutation(res,str_head_temp,str,vt_vis);

            vt_vis[i] = false;
        }

    }

    vector<string> Permutation(string str) {
        vector<string> vt_str;
        if (str.empty()) 
        {
            return vt_str;
        }

        sort(str.begin(), str.end());
        
        vector<bool> vt_vis(str.length(),false);
        Permutation(vt_str,"",str,vt_vis);
        return vt_str;
    }
};