38. arrangement of strings

The finger of the sword Offer 38. Arrangement of strings

Ideas ： to flash back

Definition

(i>0&&!isVisited[i-1]&&s[i]==s[i-1])

Ensure that repeated elimination , The prerequisite string needs to be sorted

technological process

• Sorting ensures that duplicates can be excluded
• Traversal string ,
  • If the current character is not traversed or does not meet the repetition condition , Add characters
  • Recursively call
  • Pop up the added string
• Return results

class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        string tmp;
        vector<bool> isVisited(s.size());
        sort(s.begin(),s.end());
        permutation(ans,tmp,s,isVisited);
        return ans;
    }

    void permutation(vector<string>& ans,string& tmp,string& s,vector<bool>& isVisited){
        if(tmp.size()==s.size()){
            ans.push_back(tmp);
            return;
        }

        for(int i=0;i<s.size();++i){
            if((i>0&&!isVisited[i-1]&&s[i]==s[i-1])||isVisited[i]) continue;
            tmp.push_back(s[i]);
            isVisited[i]=true;
            permutation(ans,tmp,s,isVisited);
            tmp.pop_back();
            isVisited[i]=false;
        }
    }
};

Time complexity O(nxn!) String Full Permutation O(n!), Required per spread O(n) Time generation

Spatial complexity O(n) need O(n) Stack space