字符串的排列

题目描述:

输入一个字符串,按字典序打印出该字符串中字符的所有排列。

输入描述：

输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。

输出描述：

输出为输入字符的全排列

示例：

输入：
abc
输出：
abc
acb
bac
bca
cab
cba

思路点拨：

1. 将输入的字符串看作一个字符集合，如字符集{a,b,c}。
2. 每次从字符集中取出一个字符到用于保存结果的数组result中。
3. 用一个bool类型的数组flag保存字符集中字符的状态，true表示字符集中对应下标的字符已被提取，false则表示未被提取。
4. 当flag数组全为true，表示一次字符排列已完成，保存result中的字符集。
5. 进行回溯，就是还原现场，删除result数组相应元素，并将flag中相应字符状态置为false，再递归算出下一种情况。
6. 重复以上步骤n次，其中n为字符串长度。

根据以上分析，可以采用dfs进行深搜。代码如下：

void PermutationHelper(string str, vector<string> &result);

vector<string> Permutation(string str) {
    vector<string> result;  //用于保存全排列结果

    if (str.empty())
        return result;

    PermutationHelper(str, result);
    return result;
}
void PermutationHelper(string str, vector<string> &result){ 
    static string temp;             //用于保存一次排列的字符串
    bool temp_tag = true;           //一次排列是否完成
    static bool flag[10] = {false}; //标记数组
  
    for (size_t i = 0; i < str.size(); i++) {
        /*该字符未被提取*/
        if (!flag[i]) {
            /*每次从字符集中提取出一个未被提取的字符到temp中*/
            temp.push_back(str[i]); 
            flag[i] = true;
            /*递归提取下一个字符*/
            PermutationHelper(str, result);
            /*回朔，恢复该字符的状态，并将其从temp中删除*/
            flag[i] = false;    
            temp.erase(temp.size() - 1);
        }
    }
    /*判断字符串中字符是否一全部提取*/
    for (int i = 0; i < str.size(); i++) {
        if (!flag[i]){
            temp_tag = false;
            break;
        }
    }
    /*一次排序已完成，保存结果到result中*/
    if (temp_tag) {
        result.emplace_back(temp);
    }
}

以上代码在输入字符串全部字符唯一时能正确运行，而一旦字符串中出现重复字符，输出结果就与预期不同。
比如,输入字符串为aab，期望的结果为{aabyaba,baa}，而使用上述代码的输出为{aab,aba,aab,aba,baa,baa}，重复的排列被一起保存到输出了。出现以上情况是由于未考虑重复字符的情况，现对字符串中有重复字符进行考虑。

• 当字符集中存在相同的字符时，在该位置只需提取一次该字符，因为再次提取相同的字符，后续排列在第一次提取就已经出现了。比如aab在第一次，只提取一次a，则结果就不会出现两个aab和aba的情况；
• 当提取出一个字符（该字符在字符集中有相同的字符），需要记录当前字符集中该字符是否唯一，对于不唯一时，也只提取一次即可。同样，对于aaab，当第一个为a，提取第二个时，由于字符集中还有两个a，也只需提取一次，则结果中aaab就只会出现一次。

由上述分析，需要记录字符集中相同字符的个数，由字符-个数的key-value关系，采用map来记录字符集中出现的字符以及相应的个数。

最后代码如下：

void PermutationHelper(string str, map<char, int> count, vector<string> &result);

vector<string> Permutation(string str) {
   vector<string> result;  //用于保存结果。
   map<char, int> count;   //保存字符集中出现字符的个数。

   if (str.empty())
       return result;
   /*初始化count，将字符集中出现的字符以及次数记录*/
   for (auto item : str)
       ++count[item];
   PermutationHelper(str, count, result);
   return result;
}

void PermutationHelper(string str, map<char, int> count, vector<string> &result){
   static string temp;             //用于保存一次排列的字符串
   bool temp_tag = true;           //一次排列是否完成
   static bool flag[10] = {false}; //标记数组
   int num = 0;                    //字符集剩余字符中某个字符的相同个数

   for (size_t i = 0; i < str.size(); i++) {
       if (flag[i])
           continue;
       /*由于输入字符串是按字典排序，相同的字符一定排列在一起。
        *因此，只需改变i的值，取相同字符中最后一个即可。
        */
       if (--count[str[i]] > 0)
           continue;
       /*记录该字符*/
       temp.push_back(str[i]);
       flag[i] = true;
       /*剩余字符集中该字符的个数*/
       for (size_t j = 0; j < str.size(); j++)
           if (str[j] == str[i] && !flag[j])
               num++;
       count[str[i]] = num;
       num = 0;
       /*递归提取下一个字符*/
       PermutationHelper(str, count, result);
       /*回朔，恢复现场
        *恢复该字符的状态，并将其从temp中删除
        *字符集中该字符个数加一
        */
       flag[i] = false;
       ++count[str[i]];
       temp.erase(temp.size() - 1);
   }
   /*判断字符串中字符是否一全部提取*/
   for (int i = 0; i < str.size(); i++) {
       if (!flag[i]){
           temp_tag = false;
           break;
       }
   }
   /*一次排序已完成，保存结果到result中*/
   if (temp_tag) {
       result.emplace_back(temp);
   }
}