输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：
要求：空间复杂度)
，时间复杂度
要求：空间复杂度
[编程题]字符串的排列
class Solution {
public:
void solve(vector<string> &ans, string &str, int pos, int arr[], int n){
if(pos == n){
string tmp = "";
int flag = 1;
for(int i=0;i<pos;i++) tmp += str[arr[i]];
for(int i=0;i<ans.size();i++) if(tmp == ans[i]) flag = 0;
if(flag) ans.push_back(tmp);
}
else for(int i=0;i<str.length();i++){
int ok = 1;
for(int j=0;j<pos;j++)
if(arr[j] == i) ok = 0;
if(ok){
arr[pos] = i;
solve(ans, str, pos+1, arr, n);
}
}
}
vector<string> Permutation(string str) {
sort(str.begin(), str.end());
vector<string> ans; int s[10];
if(!str.empty()) solve(ans, str, 0, s, str.length());
return ans;
}
};
发表于 2018-12-06 16:01:00
回复(0)
//参照剑指offer的思路
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> res;
if(str.empty())
return res;
string tmp="";
recur(str,res,tmp,0);
return res;
}
void recur(string str,vector<string> &res,string &tmp,int start){
if(start==str.size()){
res.push_back(tmp);
return;
}
for(int i=start;i<str.size();i++){
//判断要交换的字符是否相同，相同就不用交换直接跳过（除了start位置与自己交换的情况）
if(i!=start&&str[start]==str[i])
continue;
swap(str[start],str[i]);
tmp+=str[start];
recur(str,res,tmp,start+1);
tmp.pop_back();
}
}
};
发表于 2017-05-15 21:56:30
回复(5)
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<String>();
if (str == null || str.length() > 9 || str.length()==0) {
return result;
}
str = str.trim();
Permutation(str.toCharArray(), 0, result);
// HashSet<String> hs = new HashSet<String>(result); //此仅去重，没有字典序排列，可能错误
// new ArrayList<String>(hs);
Collections.sort(result); //字典序排列 有些oj要求
return result;
}
public static void Permutation(char[] data, int beginIdx,ArrayList<String> result) {
if (beginIdx == data.length) {
result.add(new String(data));
} else {
for (int i = beginIdx; i < data.length; ++i) {
//有重复字符时，跳过
if(i!=beginIdx && data[i]==data[beginIdx]) continue;
//当i==begin时，也要遍历其后面的所有字符；
//当i!=begin时，先交换，使第begin位取到不同的可能字符，再遍历后面的字符
char temp = data[beginIdx];
data[beginIdx] = data[i];
data[i] = temp;
Permutation(data, beginIdx + 1, result);
//为了防止重复的情况，还需要将begin处的元素重新换回来 恢复打扫战场，恢复为原来子串， data共享
temp = data[beginIdx];
data[beginIdx] = data[i];
data[i] = temp;
/* 举例来说“b(acd)” acd排列 ，为什么使用了两次swap函数? 函数栈变化恢复 ， "acd第一次输出 cda后，完全退栈 返回data应该还是acd"
交换栈 退栈
bacd bacd
bcad bcad
bcda 打印 -> bcda
*/
}
}
}
编辑于 2015-11-18 16:51:40
回复(5)
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> out;
int len = str.length();
if(len == 0)
return out;
char* p = (char *)malloc((len+1)*sizeof(char));
str.copy(p,len,0);
//全排列，迭代
myPermutation(p,0,len,out);
//字典序排序
sort(out.begin(),out.end());
//去除重复项
for(auto it = out.begin()+1;it!=out.end();){
if(*it == *(it-1))
it = out.erase(it);
else
it++;
}
return out;
}
void myPermutation(char* p,int k,int m,vector<string>& out){
if(k == m){
//将结果存入out中
string s;
for(int i = 0;i<m;++i)
s+=p[i];
out.push_back(s);
return ;
}
for(int i = k;i<m;++i){
swap(p[k],p[i]);
myPermutation(p,k+1,m,out);
swap(p[k],p[i]);
}
}
};
发表于 2017-02-06 14:50:42
回复(1)
全排列算法：从第一个元素开始，对每个元素，分别与它后面不相同的数交换
class Solution {
public:
vector Permutation(string str) {
vector res;
int n = str.length();
helper(str, res, 0, n-1);
sort(res.begin(),res.end());
return res;
}
void helper(string &str, vector &res, int begin, int end){
if(begin == end){
res.emplace_back(str);
return ;
}
for(int i = begin; i <= end; ++i){
if(!has_duplicate(str, begin, i)){
if(str[begin] != str[i]){
swap(str[begin], str[i]);
}
helper(str, res, begin + 1, end);
if(str[begin] != str[i]){
swap(str[begin], str[i]);
}
}
}
}
// begin~k-1有没有重复元素
bool has_duplicate(string &str, int begin, int k){
for (int i = begin; i < k; ++i) {
if(str[i] == str[k]){
return true;
}
}
return false;
}
};另一种解法，dfs
vector<string> Permutation_dfs(string str) {
vector<string> res;
int n = str.length();
if(n == 0){
return res;
}
sort(str.begin(), str.end());
vector<bool> visited(n, false);
string res_str = "";
dfs_helper(res, str, res_str, visited);
return res;
}
void dfs_helper(vector<string> &res, string &str, string &res_str, vector<bool> &visited){
if(res_str.length() == str.length()){
res.push_back(res_str);
return ;
}
for(int i = 0; i < str.length(); ++i){
if(visited[i]){
continue;
}
if(i != 0 && !visited[i - 1] && str[i] == str[i - 1]){
continue;
}
visited[i] = true;
res_str.push_back(str[i]);
dfs_helper(res, str, res_str, visited);
res_str.pop_back();
visited[i] = false;
}
}
编辑于 2019-04-11 22:30:24
回复(3)
算法思路:
1)n个元素的全排列=(n-1个元素的全排列)+(另一个元素作为前缀)
2)出口:如果只有一个元素的全排列,则说明已经排完,则输出数组;
3)不断将每个元素放左第一个元素,然后将它作为前缀,并将其余元素继续全排列
public ArrayList<String>Permutation(String str){
ArrayList<String>result=new ArrayList<>();
if(null==str||str.length()<1){
return result;
}
char[]charArray=str.toCharArray();
HashSet<String>mediateResult=new HashSet<>();
fullPerm(mediateResult,charArray,0,charArray.length-1);
result.addAll(mediateResult);
Collections.sort(result);
return result;
}
private void fullPerm(HashSet<String>intermediateResult,char[]charArray,int start,int end){
if(start==end){
StringBuilder sb=new StringBuilder();
for(char c:charArray){
sb.append(c);
}
interMediateResult.add(sb.toString());
return;
}else{
for(int i=start;i<=end;++i){
swap(charArray,start,i);
fullPerm(interMediateResult,charArray,start+1,end);
swap(charArray,start,i);
}
}
}
发表于 2017-01-04 10:14:29
回复(1)
我自己先写了一个标准的解法：通过交换遍历第k位可能的所有字符
void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
{
if(k == str.size() - 1)
ans.push_back(str);
unordered_set<char> us; //记录出现过的字符
sort(str.begin() + k, str.end()); //保证按字典序输出
for(int i = k; i < str.size(); i++)
{
if(us.find(str[i]) == us.end()) //只和没交换过的换
{
us.insert(str[i]);
swap(str[i], str[k]);
PermutationHelp(ans, k + 1, str);
swap(str[i], str[k]); //复位
}
}
}
vector<string> Permutation(string str) {
vector<string> ans;
PermutationHelp(ans, 0, str);
return ans;
}
然后，我随意的尝试调整了一下代码，
把递归中的复位的swap去掉，排序去掉，改为最开始一次性排序。居然也通过了。可是我没理清楚为什么？
void PermutationHelp(vector<string> &ans, int k, string str) //遍历第k位的所有可能
{
if(k == str.size() - 1)
ans.push_back(str);
for(int i = k; i < str.size(); i++)
{
if(i != k && str[k] == str[i])
continue;
swap(str[i], str[k]);
PermutationHelp(ans, k + 1, str);
}
}
vector<string> Permutation(string str) {
sort(str.begin(), str.end());
vector<string> ans;
PermutationHelp(ans, 0, str);
return ans;
}
编辑于 2018-12-26 14:11:30
回复(49)
class Solution {
public:
set<string> res;
void fun(string str, int pos)
{
if (pos == str.length())
{
res.insert(str);
return;
}
for (int i = pos; i < str.length(); ++i)
{
swap(str[i], str[pos]);
fun(str, pos + 1);
swap(str[i], str[pos]);
}
}
vector<string> Permutation(string str) {
res.clear();
vector<string> st;
if (str.length() == 0)return st;
fun(str, 0);
set<string>::iterator it;
for (it = res.begin(); it != res.end(); ++it)
st.push_back(*it);
return st;
}
};
发表于 2016-08-01 15:22:53
回复(5)
分为两步：
- 求所有可能在第一个位置的字符，即把第一个字符和后面的依次交换
- 固定第一个字符，求后面所有字符的排列。后面所有的字符又可看成第一个字符跟后面所有的字符的排列。典型的递归思路
# -*- coding:utf-8 -*-
class Solution:
def Permutation(self, ss):
if not ss:
return []
def Permutation(startIdx):
if startIdx >= len(arrSs):
clone = ''.join(arrSs)
res.append(clone)
else:
changeIdx = startIdx
while changeIdx < len(arrSs):
arrSs[changeIdx], arrSs[startIdx] = arrSs[startIdx], arrSs[changeIdx]
Permutation(startIdx + 1)
arrSs[changeIdx], arrSs[startIdx] = arrSs[startIdx], arrSs[changeIdx]
changeIdx += 1
res = []
arrSs = list(ss)
Permutation(0)
res = list(set(res))
return sorted(res)
发表于 2016-07-26 09:22:04
回复(0)
基于回溯法思想：
Java代码:
import java.util.List;
import java.util.Collections;
import java.util.ArrayList;
public class Solution {
public static void main(String[] args) {
Solution p = new Solution();
System.out.println(p.Permutation("abc").toString());
}
public ArrayList<String> Permutation(String str) {
List<String> res = new ArrayList<>();
if (str != null && str.length() > 0) {
PermutationHelper(str.toCharArray(), 0, res);
Collections.sort(res);
}
return (ArrayList)res;
}
public void PermutationHelper(char[] cs, int i, List<String> list) {
if (i == cs.length - 1) {
String val = String.valueOf(cs);
if (!list.contains(val))
list.add(val);
} else {
for (int j = i; j < cs.length; j++) {
swap(cs, i, j);
PermutationHelper(cs, i+1, list);
swap(cs, i, j);
}
}
}
public void swap(char[] cs, int i, int j) {
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}
编辑于 2018-03-20 19:17:11
回复(55)
//利用STL中的next_permutation全排列函数
//next_permutation函数会取得[first,last)所标示序列的下一个排列组合，
//如果没有下一个排列组合返回false，有则返回true
class Solution {
public:
vector<string> Permutation(string str) {
vector<string> ret;
if(str.empty())
return ret;
sort(str.begin(),str.end());
ret.push_back(str);
while(next_permutation(str.begin(),str.end()))
ret.push_back(str);
return ret;
}
};
//TODO:具体实现，递归和非递归2种方法
编辑于 2016-07-19 22:41:19
回复(0)
求助，JAVA怎么这样都能超时呢？
“qwertyuio” 运行超时:您的程序未能在规定时间内运行结束，请检查是否循环有错或算法复杂度过大。
代码如下：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return string字符串ArrayList
*/
public ArrayList<String> Permutation (String str) {
// write code here
ArrayList<String> result = new ArrayList<String>();
char[] array = str.toCharArray();
Arrays.sort(array);
do {
result.add(new String(array));
} while(nextPermutation(array));
return result;
}
public boolean nextPermutation(char[] array) {
// 找较小值
int len = array.length;
int i = len-2;
while(i>=0 && array[i]>=array[i+1]) i--;
if(i<0) return false;
// 找较大值
int j = len-1;
while(j>=0 && array[j]<=array[i]) j--;
// 交换较小和较大值
swap(array, i, j);
// 反转升序区
reverse(array, i+1);
return true;
}
public void swap(char[] array, int i, int j) {
if(i!=j) {
char temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
public void reverse(char[] array, int start) {
int left = start;
int right = array.length-1;
while(left<right) {
swap(array, left, right);
left++;
right--;
}
}
}
发表于 2022-08-01 14:42:01
回复(0)
class Solution { public: vector<string> Permutation(string str) { vector<string> res;//定义一个字符串数组，用来保存所有排列的字符串 if(str.size()==0)//字符串为空 return res; Permutation(res,str,0);//调用字符串排列函数 sort(res.begin(),res.end());//对res字符串数组进行升序排列，不然测试不通过 return res;//返回 } void Permutation(vector<string> &res,string str,int begin){ if(begin==str.size()-1)//遍历到字符串结尾，将其中一个字符串压入数组 res.push_back(str); for(int i=begin;i<str.size();++i){//i从begin开始，依次交换 if(i!=begin&&str[i]==str[begin])//当遇到重复字符，跳过 continue; swap(str[i],str[begin]);//依次交换 Permutation(res,str,begin+1);//对上一个交换结果的下一个字符依次交换 swap(str[i],str[begin]);//begin交换回来，与下一个i交换 } } };
编辑于 2019-03-25 08:40:36
回复(0)
function Permutation(str)
{
if(str.length==0) return []
var array = [str[0]]
for(let j = 1;j<str.length;j++){
array = f(array,str[j])
}
return [...new Set(array)].sort()
/*
* 下面的 f 函数是向字符串数组 a 中插入一个新字符,返回新的全排列数组,
* 例如向['aa']插入'b'得到['baa','aba','aab']
*/
function f(a,ch){
var o = []
for(let i=0;i<=a[0].length;i++){
o = o.concat(a.map(x=>x.slice(0,i)+ch+x.slice(i)))
}
return [...new Set(o)]
}
}
发表于 2019-02-12 00:34:00
回复(0)
//对比了赞最多的那个方法,思路一样,但是用hashSet解决重复值问题效率更好
public class Solution{ private HashSet<String> set =new HashSet<>(); public ArrayList<String> Permutation(String str) { ArrayList<String> list = new ArrayList<>(); if (str != null && str.length() > 0) { permutation(str, 0); list.addAll(set); Collections.sort(list); } return list;
} private void permutation(String str, int start) { char[] arr = str.toCharArray(); String r = null; if (start == str.length()-1) { r = String.valueOf(arr); set.add(r); } else { for (int i = start; i < str.length(); i++) { char temp = arr[i]; arr[i] = arr[start]; arr[start] = temp; permutation(String.valueOf(arr), start+1); temp = arr[i]; arr[i] = arr[start]; arr[start] = temp; } } }
}
发表于 2018-08-28 14:41:17
回复(0)
# -*- coding:utf-8 -*- class Solution: def Permutation(self, ss): # write code here if(len(ss) ==0): return [] if(len(ss) == 1): return list(ss) result = [] tmp = list(ss) keep = list(ss) for i in set(keep): tmp = list(ss) tmp.pop(tmp.index(i)) ans = self.Permutation(tmp) ans = [i+j for j in ans] result.extend(ans) return sorted(result)
发表于 2018-04-18 20:25:23
回复(1)
思路很简单，对于一开始stack=【】，序列abc，我们先添加一个字符进去，就是3种可能：
stack【a】，bc
stack【b】，ac
stack【c】，ab
然后怎么求解上面3个呢，递归，继续放字符进去，对于stack【a】，bc来说，就是2种可能：
stack【ab】，c
stack【ac】，b
继续递归，放字符进去，得到stack【abc】和stack【acb】，然后序列li为空了，递归结束。
那么遇到重复的字符呢？比如aba怎么办？我的语句有个set，进行了去重。不会重复放。
get=[]
def find(li,stack=[]): if not li:
return stack
for m in list(set(li)):
item=find([li[j] for j in range(len(li)) if j!=li.index(m)],stack+[m])
if item:
get.append(item)
发表于 2018-04-13 11:31:24
回复(1)
//1、应用递归，想法很简单，遍历整个字符串，固定每个字符，将除去该字符的子序列
//进行排列，并将结果合并到该字符之后
//2、检测的时候应该忽视了字典排序，感觉是只按照给定字符串的顺序检测的
import java.util.ArrayList;
public class Solution {
public ArrayList Permutation(String str) {
ArrayList list = new ArrayList();
int l = str.length();
if(l == 0 ) return list;
if(l == 1){
list.add(str);
}else{
for(int i=0;i<l;i++){
for(String tmp : Permutation(str.substring(0,i)+str.substring(i+1,l))){
String temp = str.charAt(i)+tmp;
if(!list.contains(temp)){
list.add(temp);
}
}
}
}
//Collections.sort(list);
return list;
}
}
编辑于 2017-12-28 16:32:45
回复(1)
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<String>();
if(str==null||str.length()==0)
return result;
char[] c = str.toCharArray();
Permutation(result, c, 0, c.length);
Collections.sort(result);
return result;
}
public void Permutation(ArrayList<String> list,char[] c, int star,int end){
if(star==end-1){
String result = new String(c);
if(!list.contains(result))
list.add(result);
return;
}
//交換
for(int i = star;i<end;i++){
if(i!=star&&c[star]==c[i])
continue;
char temp = c[star];
char temp2 = c[i];
c[star] = temp2;
c[i] = temp;
Permutation(list,c,star+1,end);
c[star] = temp;
c[i] = temp2;
}
}
}
编辑于 2016-04-16 17:32:33
回复(0)
问题信息
通过挑战的用户
查看代码-
2022-12-15 00:12:57
-
2022-11-26 16:04:24 -
2022-09-23 11:15:39 -
2022-09-19 16:42:37
-
2022-09-16 18:50:35
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
/** * 1、递归算法 * * 解析：http://www.cnblogs.com/cxjchen/p/3932949.html (感谢该文作者！) * * 对于无重复值的情况 * * 固定第一个字符，递归取得首位后面的各种字符串组合； * 再把第一个字符与后面每一个字符交换，并同样递归获得首位后面的字符串组合； *递归的出口，就是只剩一个字符的时候，递归的循环过程，就是从每个子串的第二个字符开始依次与第一个字符交换，然后继续处理子串。 * * 假如有重复值呢？ * *由于全排列就是从第一个数字起，每个数分别与它后面的数字交换，我们先尝试加个这样的判断——如果一个数与后面的数字相同那么这两个数就不交换了。 * 例如abb，第一个数与后面两个数交换得bab，bba。然后abb中第二个数和第三个数相同，就不用交换了。 * 但是对bab，第二个数和第三个数不 同，则需要交换，得到bba。 * 由于这里的bba和开始第一个数与第三个数交换的结果相同了，因此这个方法不行。 * * 换种思维，对abb，第一个数a与第二个数b交换得到bab，然后考虑第一个数与第三个数交换，此时由于第三个数等于第二个数， * 所以第一个数就不再用与第三个数交换了。再考虑bab，它的第二个数与第三个数交换可以解决bba。此时全排列生成完毕！ * * * @param str * @return */ public ArrayList<String> Permutation(String str){ ArrayList<String> list = new ArrayList<String>(); if(str!=null && str.length()>0){ PermutationHelper(str.toCharArray(),0,list); Collections.sort(list); } return list; } private void PermutationHelper(char[] chars,int i,ArrayList<String> list){ if(i == chars.length-1){ list.add(String.valueOf(chars)); }else{ Set<Character> charSet = new HashSet<Character>(); for(int j=i;j<chars.length;++j){ if(j==i || !charSet.contains(chars[j])){ charSet.add(chars[j]); swap(chars,i,j); PermutationHelper(chars,i+1,list); swap(chars,j,i); } } } } private void swap(char[] cs,int i,int j){ char temp = cs[i]; cs[i] = cs[j]; cs[j] = temp; } /** * 2、字典序排列算法 * * 可参考解析： http://www.cnblogs.com/pmars/archive/2013/12/04/3458289.html （感谢作者） * * 一个全排列可看做一个字符串，字符串可有前缀、后缀。 * 生成给定全排列的下一个排列.所谓一个的下一个就是这一个与下一个之间没有其他的。 * 这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。 * * [例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的987654321， * 从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。 * * 【例】 如何得到346987521的下一个 * 1，从尾部往前找第一个P(i-1) < P(i)的位置 * 3 4 6 <- 9 <- 8 <- 7 <- 5 <- 2 <- 1 * 最终找到6是第一个变小的数字，记录下6的位置i-1 * * 2，从i位置往后找到最后一个大于6的数 * 3 4 6 -> 9 -> 8 -> 7 5 2 1 * 最终找到7的位置，记录位置为m * * 3，交换位置i-1和m的值 * 3 4 7 9 8 6 5 2 1 * 4，倒序i位置后的所有数据 * 3 4 7 1 2 5 6 8 9 * 则347125689为346987521的下一个排列 * * @param str * @return */ public ArrayList<String> Permutation2(String str){ ArrayList<String> list = new ArrayList<String>(); if(str==null || str.length()==0){ return list; } char[] chars = str.toCharArray(); Arrays.sort(chars); list.add(String.valueOf(chars)); int len = chars.length; while(true){ int lIndex = len-1; int rIndex; while(lIndex>=1 && chars[lIndex-1]>=chars[lIndex]){ lIndex--; } if(lIndex == 0) break; rIndex = lIndex; while(rIndex<len && chars[rIndex]>chars[lIndex-1]){ rIndex++; } swap(chars,lIndex-1,rIndex-1); reverse(chars,lIndex); list.add(String.valueOf(chars)); } return list; } private void reverse(char[] chars,int k){ if(chars==null || chars.length<=k) return; int len = chars.length; for(int i=0;i<(len-k)/2;i++){ int m = k+i; int n = len-1-i; if(m<=n){ swap(chars,m,n); } } }