zerone

字符串的排列
字符串的排列题目描述:输入一个字符串,按字典序打印出该字符串中字符的所有排列。输入描述:输入一个字符串,长度不超过...
扫描右侧二维码阅读全文
04
2019/04

字符串的排列

字符串的排列

题目描述:

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

输入描述:

输入一个字符串,长度不超过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,则结果就不会出现两个aababa的情况;
  • 当提取出一个字符(该字符在字符集中有相同的字符),需要记录当前字符集中该字符是否唯一,对于不唯一时,也只提取一次即可。同样,对于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);
   }
}
最后修改:2019 年 04 月 07 日 03 : 12 PM
如果觉得我的文章对你有用,请随意赞赏

发表评论