字符串排列问题

题目：输入一个字符串，输出其所有排列情况。

思路：首先考虑到用回溯法来求解这道题。每次都遍历一遍字符，选择一个填入字符串，并递归的填充下一个位置。但是字符可能重复，所以需要用一个哈希表来存储字符key为字符，value为字符个数。

代码实现如下(只是实现，具体可以再优化)：

 

#include <string>
#include <vector>
#include <map>
using namespace std;
void fill(string &s, map<char, int> &c2n, vector<string> &permutations, int len);
void getPermutations(string s, vector<string> &permutations);

void getPermutations(string s, vector<string> &permutations)
{
    map<char, int> c2n;

    for(int i = 0; i < s.length(); i++)
    {
        if(c2n.find(s[i]) != c2n.end()) c2n[s[i]]++;
        else c2n[s[i]] = 1;
    }
    string ss;
    fill(ss, c2n, permutations, s.length());
}

void fill(string &s, map<char, int> &c2n, vector<string> &permutations, int len)
{
    if(s.length() == len) //填充完毕

    {
        permutations.push_back(s);
        return;
    }

    //遍历哈希表

    for(map<char, int>::iterator it = c2n.begin(); it != c2n.end(); it++)
    {
        if(it->second > 0) //个数大于0

        {
            s.push_back(it->first); //填充字符串

            it->second--; //个数减1

            fill(s, c2n, permutations, len); //继续填充

            s.erase(s.length() - 1); //删除该字符

            it->second++; //个数加1

           //回溯

        }
    }
}