剑指offer：字符串的排列（划分子问题）

问题描述：

求解一个字符串中字符的全排列。

如：给定字符串”abc“

求出全排列： abc, acb, bac, bca, cad, cba

思路：

这道题排列不是问题，问题是方法不对会导致结果有重复元素。如果不能够一次性不重复排列，则会在去重上大费功夫。

这个问题我们不难想到，与“青蛙跳台阶”、“斐波那契数列”等问题解决方法有异曲同工之妙，仔细看来，这个问题也是可以划分为子问题，解决子问题进而逐步解决整体。但是，什么是子问题呢？

举个例子，我们用输入字符串 “abcd“ 来说明：

（1）我们要求abcd的全排列，就可以分别以 a, b, c, d 开头，然后求 bcd, acd, bad, bca 的全排列。

（2）循环求上述四种情况，对于其中之一 a开头，后接bcd的情况，又可以对子串”bcd“进行（1）操作——即求bcd全排列。

（3）直到子问题级别到达只剩一个子串的全排列时候，就可以递归返回上一层了。

解决方法 - java代码：

public class 字符串的排列 { public static List permutation(String str){ if(str == null str.length() == 0){//如果字符串为空，直接返回空 return null; } List list = new ArrayList<>();//实例化一个容器，用来存放全排列结果 permutationCore(str.toCharArray(), 0, list); } public static void permutationCore(char[] chs, int index, List list){ if(index == chs.length){//上述abcd，当index移动到结尾字符d时候，可以选择把abcd加入list了 list.add(String.valueOf(chs)); } for(int i = index; i < chs.length; i++){ //i从index到结尾下标，可以使每次问题字符串的开头字符遍历完 //第一次：a bcd //第二次：b acd //...... char tmp = chs[i]; chs[i] = chs[index]; chs[index] = tmp; permutationCore(chs, index + 1, list);//解决当前字符开头的子串对应的子问题，如bcd, acd... //子问题解决完毕后，还需要恢复 //如第二次循环前面str变成了bacd //接下来还有再变回abcd，才能继续下一轮该表首字符 tmp = chs[i]; chs[i] = chs[index]; chs[index] = tmp; } } public static void main(String[] args) {//测试程序 String str = "abcd"; List list = permutation(str); list.forEach(c -> System.out.print(c + " - ")); } }

运行结果：

abcd - abdc - acbd - acdb - adcb - adbc - bacd - badc - bcad - bcda - bdca - bdac - cbad - cbda - cabd - cadb - cdab - cdba - dbca - dbac - dcba - dcab - dacb - dabc -

---