【剑指offer】面试题28：字符串的排列

题目：

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

思路：

这个不是书上的思路：每次放一个字母在cur位置，cur从0开始。放哪个字母呢？因为输入str是升序的，所以顺序地取str元素；考虑到重复的问题，每次统计结果串resstr中和str中元素出现的次数，只有当前者的次数小于后者的次数时才放置。直到放置到str长度的位置，即形成一个串。

代码：

class Solution {
public:
    vector<string> Permutation(string str) {
        vector<string>  res;
        
        if(str.size()==0)  return res;//这个还是需要的
        
        permutation_core(str,str,0,res);
        
        return res;
    }
private:
    void permutation_core(string str, string resstr, int cur, vector<string> &res)
    {
        if(cur==str.size())
        {
            res.push_back(resstr);
            
            return ;//不要忘了这里的return，或者下面有else
        }
        /*禁止重复
        for(int i=0;i<str.size();++i)
        {
            
            int ok=1;
            for(int j=0;j<cur;++j)
                if(resstr[j]==str[i])  ok=0;
            if(ok)
            {
                resstr[cur]=str[i];
                permutation_core(str,resstr,cur+1,res);
            }
        }*/
        for(int i=0;i<str.size();++i)
        if(i==0 || str[i]!=str[i-1])
        {
            int c1=0,c2=0;
            for(int j=0;j<cur;++j)  if(resstr[j]==str[i])  c1++;
            for(int j=0;j<str.size();++j)  if(str[j]==str[i])  c2++;
            if(c1<c2)
            {
                resstr[cur]=str[i];
                permutation_core(str,resstr,cur+1,res);
            }
        }
    }
};