字符串的全排列(输入一个字符串,按字典序打印出该字符串中字符的所有排列。)
字符串排列
题目描述:
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
输入描述:
输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
分析:
固定第一个字符,递归取得首位后面的各种字符串组合;再将第一个字符与后面每一个字符交换,同样递归获得其字符串组合;每次递归都是到最后一位时结束,递归的循环过程,就是从每个子串的第二个字符开始依次与第一个字符交换,然后继续处理子串。
图解:
递归过程的程序图解:
代码:
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> result = new ArrayList<>();
if(str.length()==0 ||str == null){
return result;
}
PermutationHelper(str.toCharArray(),0,result);
Collections.sort(result);
return result;
}
private void PermutationHelper(char[] chars,int i,ArrayList<String> result){
//已经递归到了字符串最后一位,判断集合中有没有这个字符串,没有则加入
if(i== chars.length-1){
if(!result.contains(new String(chars))){
result.add(new String(chars));
return;
}
}else{
//首次传进来的i为0,代表首位字符
//依次处理i与i后面的每个字符(索引j)交换
for(int j=i; j<chars.length; j++){
swap(chars,i,j);//交换
PermutationHelper(chars,i+1,result);//继续递归交换后的子串
swap(chars,i,j);//还原
}
}
}
private void swap(char[] chars,int i,int j){
if(i != j){
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
}
}
}
永恒之秋: 合法性校验不对吧,比如4(4) 这种只有应该算是非法的,但是你的规则里面没有判断
不哩不哩左卫门8: 图片多大
魅影之星辰: 有图片吗?
CHENGJL717: 请问下这个是什么数据啊
喜欢coding和curry的boy: 优雅,同学想问一下,右-下-左-上,这个优先级是根据什么排除来的呢,右-下这个两个优先级高能理解,左-上这是为什么呢