建设网站的方案,职业技能证书查询入口,在线视频网站怎么做,网站建设的总体设计字符串的全排列 题目#xff1a;输入一个字符串#xff0c;打印出改字符串中所有字符的所有排列。例如输入字符串abc#xff0c;那么打印出由a#xff0c;b#xff0c;c字符组成的所有字符串#xff1a;abc#xff0c;acb#xff0c;bac#xff0c;bca#xff0c;cab…字符串的全排列 题目输入一个字符串打印出改字符串中所有字符的所有排列。例如输入字符串abc那么打印出由abc字符组成的所有字符串abcacbbacbcacabcba 如何求解全排列这个问题初看还是比较复杂的在之前的文章 数据结构与算法–代码完整性案例分析中我们在解决问题 “打印1 到最大的n位数” 的时候也用了全排列的方式是解决思路是将1~n 位看成独立的一位然后每一位都可能是 0 ~ 9 的组合这样递归去排列每一位。 借鉴上文中的这题的思路进行全排列看似能找到解决方案但是此处又有所不同因为上文中全排列是按位来枚举此处不行不能重复例如abc无法出现 aaa的排列字符串。 分析 借鉴之前文章中的全排列思想我们还是逐个字符串分析将字符串看成是两部分组成第一部分是第一个字符第二部分是后面所有字符串。 观察如上案例我们看到我们固定第一个字符然后求后面字符的全排列 接着我们固定后面字符的第一个字符再求后面字符的全排列依次类推这个步骤我们可以通过递归来实现 在观察看以上三种情况第一个将a与第一个字符交换得第二个将a与第二个字符交换三个将a与第三个字符交换 得到结论当固定第一个字符时候我们将第一个字符分别与后面的n个字符分别交换得到第一个字符的全排列 接着固定第一个字符从第二个字符开始求第二个字符的全排列这样就避免了出现aaa的情况并且也可以通过递归去解决此问题 通过如上分析有如下代码
/*** 求字符串的全排列** author liaojiamin* Date:Created in 12:07 2021/5/24*/
public class Permutation {public static void main(String[] args) {permutationArray(ertgf);}public static void permutationArray(String arr) {char[] pChars arr.toCharArray();permutationArray(pChars, 0);}public static void permutationArray(char[] pChars, Integer start){if(pChars null || pChars.length 1 || start pChars.length - 1){printArray(pChars);}for (int i start;ipChars.length-1;i){char temp pChars[i];pChars[i] pChars[start];pChars[start] temp;permutationArray(pChars, start 1);temp pChars[i];pChars[i] pChars[start];pChars[start] temp;}}public static void printArray(char[] pChars){if(pChars null || pChars.length 1){return;}for (char pChar : pChars) {System.out.print(pChar,);}System.out.println();}
}字符串组合 以上我们解决了字符串的全排列问题如果我们需要得到字符串的所有组合应该怎么办 还是输入三个字符abc那么会有如下组合a,b,c,ab,ac,bc,abc 如果我们安如上思路进行交换虽然能得到不同的排列但是得到的确实同一个组合例如ab和ba是不同的排列但是只是一个组合。 我们将组合问题归类如下数学描述 如果输入n个字符则这n个字符能构成长度为 1 ~ n de zuhe在求解n个字符 的 长度为 m的组合1m n的组合时候我们还是同上面思路将n个字符串分为两部分第一个字符和其余所有字符 如果第一个字符参与组合则下一步在剩余 n-1个字符中挑选m - 1个如果第一个字符不参与组合则下一步在剩余 n-1个字符中挑选m个 依次按如上逻辑执行每一个位置的逻辑直到 n 字符到达最后一个字符或者获取到m个字符为止 根据如上分析有如下代码 public static void main(String[] args) {permutationArray(ertgf);combination(abcde.toCharArray());}public static void combination(char[] pChars){if(pChars null){return;}StackCharacter combinaChar new Stack();for (Integer i 1; i pChars.length; i) {combination(pChars, 0, i, combinaChar);}}/*** 求解字符串的所有组合* */public static void combination(char[] pChars, Integer begin, Integer number, StackCharacter combinaChar){if(number 0){System.out.println(combinaChar.toString());return;}if(begin pChars.length){return;}//第一个字符放入组合中combinaChar.push(pChars[begin]);combination(pChars, begin 1, number-1, combinaChar);//第一个字符不放入组合中combinaChar.pop();combination(pChars, begin1, number, combinaChar);}上一篇数据结构与算法–二叉查找树转顺序排列双向链表 下一篇数据结构与算法-- 八皇后问题两种实现方案