输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。
数据范围：
要求：空间复杂度)
，时间复杂度
要求：空间复杂度
[编程题]字符串的排列
HashSet<String> res=new HashSet<>();
public ArrayList<String> Permutation (String str) {
// write code here
dfs(str.toCharArray() ,new boolean[str.length()] ,new StringBuilder());
return new ArrayList<String>(res);
}
public void dfs(char[] cs ,boolean[] flag ,StringBuilder sb){
if(sb.length()==cs.length){
res.add(sb.toString());
return;
}
for(int i=0;i<cs.length;i++){
if(flag[i]){
continue;
}
flag[i]=true;
sb.append(cs[i]);
dfs(cs ,flag ,sb);
sb.deleteCharAt(sb.length()-1);
flag[i]=false;
}
}
发表于 2024-03-02 15:02:26
回复(0)
/*
全排列版本
*/
public class Solution {
public ArrayList<String> Permutation (String str) {
// write code here
char[] charArray = str.toCharArray();
Arrays.sort(charArray);
str = new String(charArray);
ArrayList<String> res = new ArrayList<>();
String list = "";
boolean[] visit = new boolean[str.length()];
dfs(str,res,list,visit);
return res;
}
private void dfs(String str,ArrayList<String> res,String list,boolean[] visit){
if(str.length() == list.length()){
res.add(list);
return;
}
for(int i =0;i<str.length();i++){
if(visit[i] || i>0&&str.charAt(i)==str.charAt(i-1) && visit[i-1]){
continue;
}
visit[i] = true;
list += str.charAt(i);
dfs(str,res,list,visit);
list = list.replaceAll(".$","");
visit[i] = false;
}
}
}
发表于 2024-01-30 10:55:41
回复(0)
递归
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return string字符串ArrayList
*/
public ArrayList<String> Permutation (String str) {
// write code here
if (str.length() < 2) {
return new ArrayList<String>(Arrays.asList(str));
}
ArrayList<String> possibles = new ArrayList<String>();
for (int i = 0; i < str.length(); i++) {
String prefix = String.valueOf(str.charAt(i));
String leftPart = str.substring(0, i);
// Skip duplicates
if (leftPart.contains(prefix)) {
continue;
}
ArrayList<String> results = Permutation(
// String without current character
leftPart + str.substring(i + 1, str.length())
);
results.forEach((result) -> {
possibles.add(prefix + result);
});
}
return possibles;
}
}
发表于 2023-10-05 20:16:50
回复(0)
public ArrayList<String> Permutation (String str) {
// 全排列
//String变char[]
char[] charrr=str.toCharArray();//String变char[]:str.toCharArray()
//排序（去重必然排序
Arrays.sort(charrr);
boolean[] used=new boolean[str.length()];
ArrayList<String> ans=new ArrayList<>();
ArrayList<Character> list=new ArrayList<>();//作为path
build(charrr,used,ans,list);
return ans;
}
public void build(char[] charrr,boolean[] used,ArrayList<String> ans,ArrayList<Character> list){
//截至条件:list.size()==char.length
//把char拼接到String上 用StringBuilder
if(list.size()==charrr.length){
StringBuilder sb=new StringBuilder();
for(int i=0;i<list.size();i++){
sb.append(list.get(i));
}
ans.add(sb.toString()); //把StringBuilder变成String, sb.toString()
return;
}
for(int i=0;i<charrr.length;i++){
//剪枝
//被用过是true
if(used[i]==true) continue;
if(i>0&&charrr[i]==charrr[i-1]&&used[i-1]==true) continue;
list.add(charrr[i]);
used[i]=true;
build(charrr,used,ans,list);
list.remove(list.size()-1);
used[i]=false;
}
}
发表于 2023-07-15 13:45:28
回复(0)
交换的思路，为啥会超时呢？之前通过的代码，现在超时了
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list = new ArrayList<String>();
if(str!=null&&str.length()>0) {
helper(str.toCharArray(), 0, list);
Collections.sort(list);
}
return list;
}
public void helper(char[] chars, int i, ArrayList<String> list) {
int len = chars.length;
if(i==len-1) {
String s = String.valueOf(chars);
if(!list.contains(s)){
list.add(s);
}
} else{
for(int j=i; j<len; j++) {
swap(chars, i, j);
helper(chars, i+1, list);
swap(chars, i, j);
}
}
}
public void swap(char[] cs, int i, int j){
char temp = cs[i];
cs[i] = cs[j];
cs[j] = temp;
}
}
发表于 2023-06-05 16:03:29
回复(0)
public class Solution {
public ArrayList<String> Permutation(String str) {
// 将字符串转为字符数组
char[] sArray = str.toCharArray();
// 排序，为了后面对树层去重
Arrays.sort(sArray);
// 路径
LinkedList<Character> track = new LinkedList<>();
// 结果集
ArrayList<String> ans = new ArrayList<>();
// 辅助树枝去重和树层去重
boolean[] used = new boolean[sArray.length];
backTrack(sArray, track, ans, used);
return ans;
}
private void backTrack(char[] sArray, LinkedList<Character> track,
ArrayList<String> ans, boolean[] used) {
//收获结果
if (sArray.length == track.size()) {
ans.add(parseToString(track));
return;
}
for (int i = 0; i < sArray.length; i++) {
// 同一个树枝上一个数不可以出现两次
if (used[i]) {
continue;
}
// 同一层不能选择同一个数
if (i > 0 && sArray[i] == sArray[i - 1] && !used[i - 1]) {
continue;
}
// 标记本次选择
used[i] = true;
// 做出选择
track.addLast(sArray[i]);
backTrack(sArray, track, ans, used);
// 撤销标记本次选择
used[i] = false;
// 撤销选择
track.removeLast();
}
}
private String parseToString(LinkedList<Character> track) {
// 将track转变为字符串返回
StringBuilder ans = new StringBuilder();
for (Character c : track) {
ans.append(c);
}
return ans.toString();
}
}
发表于 2023-05-30 21:11:59
回复(0)
本来想用全排列来做的，没想到超时了，但是通过率91.67%
import java.util.ArrayList;
import java.util.stream.Collectors;
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
char[] chars = str.toCharArray();
ArrayList<String> list = new ArrayList<String>();
if (str == null || str == "") {
list.add("");
return list;
}
per(chars, new Stack(), list, chars.length);
return list;
}
public void per(char[] arr, Stack stack, List<String> list, int size) {
if (arr.length <= 0) {
Character[] character = new Character[size];
stack.copyInto(character);
String str = Arrays.stream(character).map(String::valueOf).collect(
Collectors.joining());
if (!list.contains(str)) {
list.add(str);
}
} else {
for (int i = 0; i < arr.length; i++) {
char[] tempChars = new char[arr.length - 1];
System.arraycopy(arr, 0, tempChars, 0, i);
System.arraycopy(arr, i + 1, tempChars, i, arr.length - 1 - i);
stack.push(arr[i]);
per(tempChars, stack, list, size);
stack.pop();
}
}
}
}
发表于 2023-03-21 09:36:22
回复(0)
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
if (Objects.isNull(str) || str.isEmpty()) return new ArrayList<>();
HashSet<String> set = new HashSet<>();
generatStr(str, 0, set);
return new ArrayList(set);
}
private void generatStr(String str, int i, HashSet<String> set) {
char[] chars = str.toCharArray();
// 第i位置的字符与str后面每个位置换一遍
for (int i1 = i; i1 < chars.length; i1++) {
char temp = chars[i];
chars[i] = chars[i1];
chars[i1] = temp;
set.add(String.valueOf(chars));
// 得到的新字符串，再接着与后面的交换(如题目画的图那样)
generatStr(String.valueOf(chars), i + 1, set);
}
}
}
发表于 2023-03-09 21:48:07
回复(0)
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
char[] chars = str.toCharArray();
Permutation(chars, res, 0);
return res;
}
public void Permutation(char[] chars, ArrayList<String> res, int i) {
if(i == chars.length){
res.add(new String(chars));
return;
}
// 每一层都使用一个hashset 来保存没有重复的字符，如果有重复，则不递归尝试获取排列
HashSet<Character> temp = new HashSet<>();
// 每个j位置的数都有机会来到i位置
for (int j = i; j < chars.length; j++) {
// 只要set中不包含j索引的字符，那么递归求解
if(!temp.contains(chars[j])){
// 添加记录
temp.add(chars[j]);
// 交换位置
permutationSwap(chars, i, j);
// 递归求解
Permutation(chars, res, i+1);
// 交换回来，下次循环继续
permutationSwap(chars, i, j);
}
}
}
public void permutationSwap(char[] chars, int i, int j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
发表于 2022-11-20 13:02:05
回复(0)
import java.util.ArrayList;
import java.util.*;
public class Solution {
ArrayList<String> list = new ArrayList<>();
Map<String,Integer> map = new HashMap<>();
public ArrayList<String> Permutation(String str) {
if(str.length()==0)return list;
char[] chars = str.toCharArray();
boolean[] vis = new boolean[chars.length];
swap(chars,"",vis);
return list;
}
public void swap(char[] chars,String cur,boolean[] vis){
if(chars.length==cur.length() && !map.containsKey(cur)){
map.put(cur,1);
list.add(cur);
return;
}
for(int i = 0;i<chars.length;i++){
if(!vis[i]){
cur+=chars[i];
vis[i]=true;
swap(chars,cur,vis);
cur=cur.substring(0,cur.length()-1);
vis[i]=false;
}
}
}
}
发表于 2022-11-08 16:12:21
回复(0)
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return string字符串ArrayList
*/
public ArrayList<String> Permutation (String str) {
ArrayList<String> result = new ArrayList<String>();
StringBuilder sb = new StringBuilder();
char[] charArr = str.toCharArray();
Arrays.sort(charArr);
backTrack(result, sb, charArr, new boolean[charArr.length]);
return result;
}
private void backTrack(ArrayList<String> result, StringBuilder sb, char[] charArr, boolean[] visited) {
if (sb.length() == charArr.length) {
result.add(sb.toString());
return;
}
for (int i = 0; i < charArr.length; i++) {
if (visited[i]) continue;
if (i > 0 && charArr[i - 1] == charArr[i] && visited[i - 1]) continue;
visited[i] = true;
sb.append(charArr[i]);
backTrack(result, sb, charArr, visited);
visited[i] = false;
sb.deleteCharAt(sb.length() - 1);
}
}
}
发表于 2022-09-16 09:25:21
回复(0)
import java.util.ArrayList;
public class Solution
{//1
public ArrayList<String> PermutationHelp(StringBuilder str){//2
ArrayList<String> result = new ArrayList<String>();
if(str.length() == 1)result.add(str.toString());
else{//3
for(int i = 0; i < str.length(); i++){//4
if(i== 0 || str.charAt(i) != str.charAt(0)){//5
char temp = str.charAt(i);
str.setCharAt(i, str.charAt(0));
str.setCharAt(0, temp);
ArrayList<String> newResult = PermutationHelp(new StringBuilder(str.substring(1)));
for(int j =0; j < newResult.size(); j++)
result.add(str.substring(0,1)+newResult.get(j));
//用完还是要放回去的
temp = str.charAt(0);
str.setCharAt(0, str.charAt(i));
str.setCharAt(i, temp);
}//5
}//4
//需要在做一个排序操作
}//3
return result;
}//2
public ArrayList<String> Permutation(String str) {
StringBuilder strBuilder = new StringBuilder(str);
ArrayList<String> result = PermutationHelp(strBuilder);
return result;
}
}//1
public class Solution
{//1
public ArrayList<String> PermutationHelp(StringBuilder str){//2
ArrayList<String> result = new ArrayList<String>();
if(str.length() == 1)result.add(str.toString());
else{//3
for(int i = 0; i < str.length(); i++){//4
if(i== 0 || str.charAt(i) != str.charAt(0)){//5
char temp = str.charAt(i);
str.setCharAt(i, str.charAt(0));
str.setCharAt(0, temp);
ArrayList<String> newResult = PermutationHelp(new StringBuilder(str.substring(1)));
for(int j =0; j < newResult.size(); j++)
result.add(str.substring(0,1)+newResult.get(j));
//用完还是要放回去的
temp = str.charAt(0);
str.setCharAt(0, str.charAt(i));
str.setCharAt(i, temp);
}//5
}//4
//需要在做一个排序操作
}//3
return result;
}//2
public ArrayList<String> Permutation(String str) {
StringBuilder strBuilder = new StringBuilder(str);
ArrayList<String> result = PermutationHelp(strBuilder);
return result;
}
}//1
发表于 2022-09-14 19:51:28
回复(0)
超时
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str string字符串
* @return string字符串ArrayList
*/
ArrayList<String> res = new ArrayList<String>();
public ArrayList<String> Permutation (String str) {
// write code here
char[] c = str.toCharArray();
Arrays.sort(c);
// 记录访问过的字符
ArrayList<Character> path = new ArrayList<Character>();
// 记录字符是否访问过
boolean[] visited = new boolean[c.length];
dfs(c,path,visited);
return res;
}
public void dfs(char[] c,ArrayList<Character> path,boolean[] visited){
// 结束条件
if(path.size() == c.length){
StringBuilder str = new StringBuilder();
for(char cc : path){
str.append(cc);
}
res.add(str.toString());
return;
}
for(int i=0; i<c.length; i++){
// 如果字符已经在path路径里面就跳过
if(visited[i]) continue;
// 如果有重复字符且前面已经处理过就跳过，注意!visited[i-1]的！非常关键，只有在回溯过后才会进入处理处理
if(i > 0 && c[i] == c[i-1] && !visited[i-1]) continue;
path.add(c[i]);
visited[i] = true;
dfs(c,path,visited);
// 回溯
path.remove(path.size()-1);
visited[i] = false;
}
}
}
发表于 2022-08-28 16:17:50
回复(0)
超时了是怎么回事，自己根据前面数组排列的题改的代码超时了，以为是自己的代码不行。使用模板速刷模式，提供的模板代码也是运行超时。测试用例"qwertyuio"
发表于 2022-08-08 16:22:53
回复(1)
问题信息
难度：
225条回答
5692收藏
250811浏览
通过挑战的用户
查看代码-
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群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：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); } } }