大厂面试: 获取字符串的全排列

一、概念

现有一个字符串，要打印出该字符串中字符的全排列。例如输入字符串abc，则打印出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。

可以基于回溯法来解决这个问题。

二、代码

public class Permutation {

//输出字符串str的全排列组合

public void dump(String str) {

List list = getPermutation(str);

for(String s:list) {

System.out.println(s);

}

}

//返回字符串str的全排列组合

public List getPermutation(String str) {

List resultList = new ArrayList<>;

//若字符串长度为0，则返回空列表

if(null==str|| str.isEmpty){

return (List)resultList;

}else {

//递归的初始值为（str数组，空的结果list，初始下标0）

backtrace(str.toCharArray,resultList,0);

Collections.sort(resultList);

return (List)resultList;

}

}

/**

* 回溯算法

* @param array 字符数组

* @param list 结果列表

* @param index 执行交换的索引

*/

private void backtrace(char[] array,List list,int index){

//若索引已到最后，则做好收集存储，并返回

if(index == array.length-1){

if(!list.contains(new String(array))){

list.add(new String(array));

return;

}

}

//若索引未到最后一个位置，则继续执行

else{

for(int j=index;j

//交换索引index和j的元素

swap(array,index,j);

//继续回溯算法

backtrace(array,list,index+1);

//再复原回去

swap(array,index,j);

}

}

}

//交换array字符数组中索引为i和j位置的元素

private void swap(char[] array, int i, int j) {

if (i != j) {

char t = array[i];

array[i] = array[j];

array[j] = t;

}

}

}

致力于C、C++、Java、Kotlin、Android、Shell、JavaScript、TypeScript、Python等编程技术的技巧经验分享。

若作品对您有帮助，请关注、分享、点赞、收藏、在看、喜欢。您的支持是我们为您提供帮助的最大动力。