剑指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 –


其他文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注