【剑指Offer面试编程题】题目1369：字符串的排列--九度OJ

题目描述：: 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

输入：

每个测试案例包括1行。

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

输出：: 对应每组数据,按字典序输出所有排列。

样例输入：

abc

BCA

样例输出：

abc

acb

bac

bca

cab

cba

ABC

ACB

BAC

BCA

CAB

CBA

【解题思路】由于需要字典序，首先肯定是要先对所给的字符串进行排序，然后很容易想到穷举法，但这边穷举法还有要避免重复，所以，有一定的技巧。我们有三个元素abb，最后输出时三元组，则我们可以将三个位置都看做由所有元素来填充的序列。负责度应该是一个n的n次方，但中间可以有一些剪枝。

由于n的大小不固定，我们没法确定是几层循环，所以只能用递归操作来进行遍历。对每一次递归调用都遍历n个元素哪个适合加入到结果队列res中，同时，我们设置一个used变量来控制某个元素是否已经在res中，避免重复添加。当检测到res的长度已经等于n，也即res中包含了所有的元素，则res中存在了一个合法的输出，我们输出结果。

当然，对于abb这种情况，我们需要对bb做特殊处理即我们不会输出1 2 3这种情况，至会输出1 3 2这种排列。具体就是当检测到某元素与之前的元素相等时我们跳过该元素。对于abb这种情况，遍历的顺序见下图。

AC code：

#include <cstdio>

#include <vector>

#include <string>

#include <iostream>

#include <algorithm>

using namespace std;

void permutation(vector<char> &res,string &str,vector<int> &used)

{

  if(res.size()==str.length())

  {

    for(int i=0;i<res.size();++i)

      printf("%c",res[i]);

    printf("\n");

    return;

  }

  for(int i=0;i<str.length();++i)

  {

    if(used[i] || (i!=0 && str[i]==str[i-1] && used[i-1]))

      continue;

    used[i]=1;

    res.push_back(str[i]);

    permutation(res,str,used);

    used[i]=0;

    res.pop_back();

  }

}

int main()

{

  string strin;

  while(cin>>strin)

  {

    vector<int> used(10,0);

    sort(strin.begin(),strin.end());

    vector<char> res;

    permutation(res,strin,used);

  }

  return 0;

}

/**************************************************************

    Problem: 1369

    User: huo_yao

    Language: C++

    Result: Accepted

    Time:530 ms

    Memory:1520 kb

****************************************************************/

巴特西

【剑指Offer面试编程题】题目1369：字符串的排列--九度OJ

最新文章

热门文章