给定一个字符串string A和其长度n，返回所有该字符串所包含字符的各种排列。要求输入字符串长度小于等于11且均为大写英文字符，排列中的字符串按字典序从大到小排序。(重复字符串不用合并)
测试样例：
"ABC"
返回：["CBA","CAB","BCA","BAC","ACB","ABC"]
[编程题]字符串排列
class Permutation {
public:
vector<string> getPermutation(string A) {
vector<string> res;
if(A.size() == 0)
return res;
permutation(A, res, 0);
sort(res.begin(), res.end(), greater<string>());//排序
return res;
}
void permutation(string A, vector<string>& res, int cur){
int len = A.size();
if(cur == len -1){//到最后一个字符，就插入结果
res.push_back(A);
return;
}
for(int i = cur; i < len; ++i){
swap(A[i], A[cur]);//交换元素
permutation(A, res, cur+1);//递归调用
swap(A[i], A[cur]);//换回来
}
}
};
发表于 2015-10-07 18:49:14
回复(3)
/*我的方法有点笨，求一个字符串的全排列，然后再从大到小排序。全排列求法是一个一个求的。首先将字符串分解成单个字符，第一次将第一个字符A拿出来，然后从第二个字符B开始向第一个字符中添加元素，第二个字符有两种添加方法：添加到第一个字符前面或后面，这样就得到两个字符串“BA”“AB”；接着添加第三个字符串，两个字符串分别有三种添加方法，例如把C添加到AB和BA中，可以从前面，中间和后面添加，分别得到三个字符串，CAB，ACB，ABC和CBA，BCA，BAC；接着将第四个字符添加到这6个字符串中.....以此类推，直到最后一个字符添加完之后，所得的字符串就是全排列。*/class Permutation { public: vector<string> getPermutation(string A) { // write code here vector<string> res;if (A == "")return res;int len = A.size();vector<string> vec;for (int i = 0; i<len; i++){string s = "";s += A[i];vec.push_back(s);}string str = "";str += vec[0];res.push_back(str);vector<string> T ;for (int i = 1; i<len; i++){vector<string> copy = res;for (int j = 0; j<copy.size(); j++){Insert(T, copy[j], vec[i]);}res = T;T.clear();}sort(res.begin(), res.end(),greater<string>());return res; } void Insert(vector<string> &vec, string str1,string str2) { int len = str1.size();string str = "";for (int i = 0; i<len+1; i++){str = "";if (i == len)str = str1 + str2;else {for (int j = 0; j < len; j++)if (j == i)str += str2 + str1[j];elsestr += str1[j];}vec.push_back(str);} } };
编辑于 2018-01-16 11:58:19
回复(0)
public ArrayList<String> getPermutation(String A) {
ArrayList<String> list = f(A);
Collections.sort(list, new Comparator<String>() {
public int compare(String o1, String o2) {
return o2.compareTo(o1);
}
});
return list;
}
private ArrayList<String> f(String A) {
ArrayList<String> list = new ArrayList<String>();
if (A == null || "".equals(A)) { //递归终止条件
list.add("");
return list;
}
char c = A.charAt(0);
String l = A.substring(1);
ArrayList<String> arr = f(l);
for (String s : arr) {
for (int i = 0; i <= s.length(); i++) {
list.add(insert(s, c, i));
}
}
return list;
}
public String insert(String s, char b, int i) { //插入字符
String a = s.substring(0, i);
String c = s.substring(i, s.length());
return a + b + c;
}
发表于 2016-08-30 16:20:22
回复(3)
class Permutation {
public:
static bool cmp(const string &a, const string &b)
{
return a > b;
}
vector<string> getPermutation(string A) {
// write code here
vector<string> result;
dfs(result, A, 0);
sort(result.begin(), result.end(),cmp);
return result;
}
void dfs(vector<string>&result, string A, int step)
{
if (step >= A.size())
{
result.push_back(A);
return;
}
for (int i = step; i < A.size(); ++i)
{
swap(A[step], A[i]);
dfs(result, A, step + 1);
swap(A[step], A[i]);
}
}
};
发表于 2016-04-19 14:53:44
回复(0)
class Permutation {
public:
vector<string> getPermutation(string A) {
vector<string> ret;
if(A.empty()) return ret;
fun(A,0,ret);
sort(ret.begin(),ret.end());
reverse(ret.begin(),ret.end());
return ret;
}
void fun(string s,int index,vector<string> &ret){
if(index==s.size()-1){
ret.push_back(s);
}
for(int i=index;i<s.size();i++){
swap(s[i],s[index]);
fun(s,index+1,ret);
swap(s[i],s[index]);
}
}
};
发表于 2015-10-01 22:53:53
回复(1)
//标志位法
class Permutation {
public:
static bool cmp(const string str1,const string str2)
{
return str1>str2;
}
void permutation(vector<string>&ans,int index,vector<int>flag,string str,string temp)
{
temp+=str[index];
flag[index]=1;
for(int i=0;i<str.size();++i)
{
if(!flag[i])
permutation(ans,i,flag,str,temp);
}
if(temp.size()==str.size()) ans.push_back(temp);
}
vector<string> getPermutation(string A) {
vector<string>res;
vector<int>state(A.size());
fill(state.begin(),state.end(),0);
string ch;
for(int i=0;i<A.size();++i)
{
ch="";
permutation(res,i,state,A,ch);
}
sort(res.begin(),res.end(),cmp);
return res;
}
};
//拆分法，可以将abcd拆分为a[bcd]、b[acd]、c[abd]、d[abc]，其中[]代表全排列
class Permutation {
public:
void permutation(string str,vector<string>&ans,int cnt)
{
if(cnt==str.size()-1) ans.push_back(str);
for(int i=cnt;i<str.size();++i)
{
swap(str[cnt],str[i]);
permutation(str,ans,cnt+1);
swap(str[cnt],str[i]);
}
}
vector<string> getPermutation(string A) {
vector<string>res;
if(A.size()<=0) return res;
permutation(A,res,0);
sort(res.begin(),res.end(),greater<string>());
return res;
}
};
编辑于 2019-05-24 21:28:39
回复(0)
class Permutation {
public: static bool cmp(string a, string b){ return a>b; } void DFS(vector<string> &v, string s, int k){ if(k==s.length()){ v.push_back(s); return; } for(int i=k;i<s.size();i++){ swap(s[i], s[k]); DFS(v, s, k+1); swap(s[i], s[k]); } }
vector<string> getPermutation(string A) {
vector<string> v;
DFS(v, A, 0);
sort(v.begin(), v.end(), cmp);
return v;
}
};
发表于 2019-03-01 02:30:10
回复(0)
class Permutation {
public:
vector<string> getPermutation(string A) {
vector<string> res;
if(A.size() == 0) return res;
if(A.size() == 1){
res.push_back(A);
return res;
}
for(int i=0; i<A.size(); ++i) {
for(auto s : getPermutation(A.substr(0, i) + A.substr(i+1, A.size()-i-1))) {
res.push_back(A.substr(i, 1) + s);
}
}
sort(res.begin(), res.end());
reverse(res.begin(), res.end());
return res;
}
};
# -*- coding:utf-8 -*- class Permutation: # A是一个字符串 def getPermutation(self, A): # 递归退出条件 if not A: return [] elif len(A) == 1: return [A] res = [] for i, c in enumerate(A): for s in self.getPermutation(A[:i] + A[i+1:]): res.append(c + s) res.sort(reverse=True) return res
发表于 2018-12-18 23:18:14
回复(0)
class Permutation {
public:
vector<string> ret;
vector<string> getPermutation(string A) {
int len = A.size();
int temp[len];
for(int i=0; i<len; i++){
temp[i] = 0;
}
int cur = 0;
calc(len, cur, temp, A);
sort(ret.begin(), ret.end(), comp);
return ret;
}
static bool comp(string s1, string s2){
return s1>s2;
}
void calc(int len, int cur, int temp[], string A){
if(len == cur){
char *ch = new char[len];
for(int j=0; j<len; j++){
ch[j] = A.at(temp[j]-1); // 注意temp[i]比实际值大1
}
string str(ch, len);
ret.push_back(str);
}else{
for(int i=0; i<len; i++){
temp[cur] = i+1;
if(judge(cur, temp)){
calc(len, cur+1, temp, A);
}
}
}
}
bool judge(int cur, int temp[]){
for(int i=0; i<cur; i++){
if(temp[i] == temp[cur]){
return false;
}
}
return true;
}
};
发表于 2017-05-27 21:41:16
回复(0)
//金典思路的c++版本，又需要可以看一下
class Permutation {
public:
template <typename T>
struct cmp
{
bool operator()(const T &x, const T &y)
{
return y<x;
}
};
string insertCharAt(string word,char c,int i){
string start=word.substr(0,i);
string end=word.substr(i);
return start+c+end;
}
vector<string> getPermutations(string A) {
vector<string> permutations;
if(A.size()==0){
permutations.push_back("");
return permutations;
}
char first=A.at(0);
string remainder=A.substr(1);
vector<string> words=getPermutations(remainder);
for(int i=0;i<words.size();i++){
string word=words[i];
for(int j=0;j<=word.size();j++){
string s=insertCharAt(word,first,j);
permutations.push_back(s);
}
}
return permutations;
}
vector<string> getPermutation(string A) {
vector<string> result=getPermutations(A);
sort(result.begin(),result.end(),cmp<string>());
return result;
}
};
发表于 2016-10-23 14:18:42
回复(0)
考察全排列，参考资料见http://blog.csdn.net/jiejinquanil/article/details/52164086
class Permutation {
public:
vector<string> vs;
void Permutatio(string A,int i){
if(A.length()==i)
vs.push_back(A);
else{
for(int j = i;j<A.length();++j){
swap(A[j],A[i]);
Permutatio(A,i+1);
swap(A[j],A[i]);
}
}
}
vector<string> getPermutation(string A) {
Permutatio(A,0);
sort(vs.begin(),vs.end());
reverse(vs.begin(),vs.end());
return vs;
}
};
发表于 2016-08-23 16:17:16
回复(1)
思路：先做全排列，然后排序。
class Permutation { public: vector<string> getPermutation(string A) { // write code here int len = A.length(); vector<string> result; myPermutation(result, A, len, 0); sort(result.begin(), result.end(), greater<string>()); return result; } void myPermutation(vector<string> &result, string &A, int len, int pos) { if(pos == len-1) { result.push_back(A); return; } for(int i = pos; i < len; i++) { swap(A[pos], A[i]); myPermutation(result, A, len, pos+1); swap(A[pos], A[i]); } } };
发表于 2016-09-07 10:44:36
回复(0)
//大家好，我是yishuihan
class Permutation {
public:
vector<string> getPermutation(string A) {
// write code here
vector<string> vec;
if(A.length()<=0) return vec;
permutation(vec,A,0);
sort(vec.begin(), vec.end(), greater<string>());
//排序，传入比较器great<string>,如果从小到大就要用less<string>;
return vec;
}
void permutation(vector<string>& vec,string A,int begin)
{
if(begin==A.length())
{
vec.push_back(A);
}
for(unsigned int i=begin;i<A.length();i++)
{
swap(A[i],A[begin]);
permutation(vec,A,begin+1);
swap(A[i],A[begin]);
}
}
};
发表于 2016-08-06 20:10:26
回复(0)
public class Permutation {
public ArrayList<String> getPermutation(String A) {
// write code here
ArrayList<String> list=new ArrayList<String>();
boolean used[]=new boolean[A.length()];
permutation(A,used,list,A.length(),0,"");
Collections.sort(list,new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
// TODO Auto-generated method stub
return o2.compareTo(o1);
}
});
return list;
}
void permutation(String a,boolean used[],ArrayList<String> list,int len,int k,String res){
if(k==len){
list.add(res);
return ;
}
for(int i=0;i<len;i++){
if(!used[i]){
used[i]=true;
res+=a.charAt(i);
permutation(a,used,list,len,k+1,res);
res=res.substring(0,res.length()-1);
used[i]=false;
}
}
}
}
发表于 2015-10-07 21:51:06
回复(1)
import java.util.*;
public class Permutation {
public ArrayList<String> getPermutation(String A) {
// write code here
ArrayList<String> list = new ArrayList<>();
permutation(list, A.toCharArray(), 0);
Collections.sort(list);
Collections.reverse(list);
return list;
}
public void permutation(ArrayList<String> list, char[] array, int k) {
if(k == array.length) {
list.add(new String(array));
return ;
}
for(int i = k; i < array.length; i++) {
swap(array, i, k);
permutation(list, array, k + 1);
swap(array, i, k);
}
}
public void swap(char[] array, int i, int j) {
if(i != j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
}
发表于 2016-06-24 21:42:48
回复(4)
我的这个python结果和答案一样啊，怎么不通过呢，有没有大佬
# -*- coding:utf-8 -*- import itertools class Permutation: # A是一个字符串 def getPermutation(self, A): # write code here res = [] if A == "": return [] lit = list(itertools.permutations(list(A), len(A))) for elem in lit: x = ''.join(elem) if x not in res: res.append(x) res.sort(reverse=True) return res
发表于 2022-10-22 21:50:41
回复(1)
class Permutation {
public:
void permuDict(vector<string> &dict, string &A, int i, vector<int>mark, string loca)
{
mark[i] = 1;
loca += A[i];
if(loca.length() == A.length())
{
dict.push_back(loca);
return;
}
else
{
for(auto j = 0; j < A.length(); j++)
if(mark[j] == 0)
permuDict(dict, A, j, mark, loca);
}
}
vector<string> getPermutation(string A) {
// write code here
vector<string>dict;
vector<int>mark(A.length(), 0);
string str="";
for(auto i = 0; i < A.length(); i++)
permuDict(dict, A, i, mark, str);
sort(std::begin(dict), std::end(dict), [](string a, string b){return a>b;});
return dict;
}
};
public:
void permuDict(vector<string> &dict, string &A, int i, vector<int>mark, string loca)
{
mark[i] = 1;
loca += A[i];
if(loca.length() == A.length())
{
dict.push_back(loca);
return;
}
else
{
for(auto j = 0; j < A.length(); j++)
if(mark[j] == 0)
permuDict(dict, A, j, mark, loca);
}
}
vector<string> getPermutation(string A) {
// write code here
vector<string>dict;
vector<int>mark(A.length(), 0);
string str="";
for(auto i = 0; i < A.length(); i++)
permuDict(dict, A, i, mark, str);
sort(std::begin(dict), std::end(dict), [](string a, string b){return a>b;});
return dict;
}
};
发表于 2020-12-17 21:22:30
回复(0)
参考下图，发现跟树的层序遍历相似，使用队列穷举，最后一次保存结果：
class Permutation {
public:
vector<string> getPermutation(string s) {
// write code here
vector<string> res;
if (s.size() == 0)
return res;
if (s.size() == 1)
{
res.push_back(s);
return res;
}
queue<string> q;
q.push(s);
for (int i = 0; i < s.size() - 1; i++)
{
int size = q.size();
while (size)
{
string str = q.front();
q.pop();
for (int j = i; j < str.size(); j++)
{
swap(str[i], str[j]);
//cout << str << endl;
//最后一次交换后保存到结果
if (i == s.size() - 2)
{
res.push_back(str);
}
q.push(str);
swap(str[i], str[j]);
}
size--;
}
}
sort(res.begin(), res.end(), greater<string>());
return res;
}
};
编辑于 2020-09-21 21:40:01
回复(0)
问题信息
难度：
73条回答
156收藏
21000浏览
通过挑战的用户
查看代码-
2022-11-30 10:37:17
-
2022-10-22 21:46:08 -
2022-10-16 17:21:41
-
2022-10-14 21:32:24
-
2022-09-03 22:30:46
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
