题解 | #字符串的排列#

跟之前那个有重复数字的数组全排列一样

class Solution {
public:
    void backtrack(vector<string> &result,string str,vector<int> &visited,string tmp,int length){
        if(tmp.size()==length){
            result.push_back(tmp);
            return;
        }
        
        for(int i=0;i<length;++i){ 
            if(visited[i]) continue;  //  纵向
            if(i>0 && str[i]==str[i-1] && !visited[i-1]) continue; // 横向
            
            visited[i] = 1;
            tmp.push_back(str[i]);
            backtrack(result,str,visited,tmp,length);
            visited[i] = 0 ;
            tmp.pop_back();
        }
    }
    
    vector<string> Permutation(string str) {
        // 这题不就是重复数组的全排列那题？
        vector<string> result;
        int length = str.size();
        if(length<=0) return result;
        
        sort(str.begin(), str.end());
        vector<int> visited(length,0);
        string tmp;
        
        backtrack(result, str, visited, tmp, length);
        return result;
    
    }
};