题目描述
编写一个方法,确定某字符串的所有排列组合。
给定一个string A和一个int n,代表字符串和其长度,请返回所有该字符串字符的排列,保证字符串长度小于等于11且字符串中字符均为大写英文字符,排列中的字符串按字典序从大到小排序。(不合并重复字符串)
测试样例:
"ABC"
返回:
["CBA","CAB","BCA","BAC","ACB","ABC"]
共有N!
个
推理过程 字符 放到前面 中间 后面
解法
迭代逐步生成(集合)
package CC150;
import java.util.ArrayList;
public class _905_字符串全排列 {
public static void main(String[] args) {
String A = "ABC";
System.out.println(solve(A));
}
private static ArrayList<String> solve(String A) {
ArrayList<String> res = new ArrayList<>();
int len = A.length();
res.add(A.charAt(0) + "");//初始化,包含第一个字符
for (int i = 1; i < len; i++) {//第二个字符插入到前面生成集合的每个元素里
ArrayList<String> res_new = new ArrayList<>();
String c = A.charAt(i) + "";//新字符
//插入到每个字符,形成一个新串
for (String str : res) {//访问上一趟集合中的每个字符串
res_new.add(c +""+ str);//前加
res_new.add(str +""+ c);//后加
for (int j = 1; j < str.length(); j++) {//中间加
res_new.add(str.substring(0, j) + c + str.substring(j));
}
}
res = res_new;//更新
}
return res;
}
}
交换法 经典回溯全排列
简洁高效,自然处理重复 但是 无法维持字典序

先纵后横
但是该算法无法直接维持字典序
static ArrayList<String> res=new ArrayList<>();//全局变量存储
public static ArrayList<String> getPermutation(String A){
char[] arr=A.toCharArray();
Arrays.sort(arr);
getPermutationCore(arr,0);
return res;
}
private static void getPermutationCore(char[] arr, int k) {
if(k==arr.length){//拍好了一中情况
res.add(new String(arr));
}
//从k位置开始的每个字符都尝试放在新排列的k的这个个位置
for (int i = k; i <arr.length ; i++) {
swap(arr,k,i);//把后面的每个字符都换到k位
getPermutationCore(arr,k+1);
swap(arr,k,i);//回溯
}
}
private static void swap(char[] arr, int k, int i) {
char tmp=arr[i];
arr[i]=arr[k];
arr[k]=tmp;
}
1949牌 类似
前缀法 (可以求第k个排列)
维持良好的字典序 入坑先入字典序小的
但是 较复杂 要处理重复 要额外处理。
每次都从头扫描 只要该字符可用,
例题 leetCode60
final static int k = 3;//我们要求的第几个字典序的排列
static int count = 0;
private static void permutation(String prefix, char[] arr) {
if (prefix.length() == arr.length) {//前缀长度=字符集长度 一个排列完成
count++;
}
if (count == k) {
System.out.println(prefix);
System.exit(0);
}
//每次都从头扫描,只要扫该字符可用,我们就附加前缀后面,前缀变长
for (int i = 0; i < arr.length; i++) {
char ch = arr[i];
//这个字符可用:pre中出现的次数<在字符集中出现的次数
if (count(prefix, ch) < count(arr, ch)) {
permutation(prefix + ch, arr);
}
}
}
private static int count(String prefix, char ch) {
int cnt = 0;
for (int i = 0; i < prefix.length(); i++) {
if (prefix.charAt(i) == ch) cnt++;
}
return cnt;
}
private static int count(char[] arr, char ch) {
int cnt = 0;
for (char c : arr) {
if (c == ch) cnt++;
}
return cnt;
}
本文作者:Author: 寒光博客
文章标题:[CC150 ]905符串全排列 三种算法
本文地址:https://dxoca.cn/Algorithm/213.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/213.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。