• 一、题目
  • 二、解题思路
  • 三、解题代码

    一、题目

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

    二、解题思路

    把一个字符串看成由两部分组成:第一部分为它的第一个字符,第二部分是后面的所有字符。

    我们求整个字符串的排列,可以看成两步:首先求所有可能出现在第一个位置的字符,即把第一个字符和后面所有的字符交换。这个时候我们仍把后面的所有字符分成两部分:后面字符的第一个字符,以及这个字符之后的所有字符。

    这其实是很典型的递归思路。

    三、解题代码

    1. public class Test {
    2. /**
    3. * 题目:输入一个字符串,打印出该字符事中字符的所有排列。例如输入字符串abc。
    4. * 则打印出由字符a、b、c 所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。
    5. *
    6. * @param chars 待排序的字符数组
    7. */
    8. public static void permutation(char[] chars) {
    9. // 输入较验
    10. if (chars == null || chars.length < 1) {
    11. return;
    12. }
    13. // 进行排列操作
    14. permutation(chars, 0);
    15. }
    16. /**
    17. * 求字符数组的排列
    18. *
    19. * @param chars 待排列的字符串
    20. * @param begin 当前处理的位置
    21. */
    22. public static void permutation(char[] chars, int begin) {
    23. // 如果是最后一个元素了,就输出排列结果
    24. if (chars.length - 1 == begin) {
    25. System.out.print(new String(chars) + " ");
    26. } else {
    27. char tmp;
    28. // 对当前还未处理的字符串进行处理,每个字符都可以作为当前处理位置的元素
    29. for (int i = begin; i < chars.length; i++) {
    30. // 下面是交换元素的位置
    31. tmp = chars[begin];
    32. chars[begin] = chars[i];
    33. chars[i] = tmp;
    34. // 处理下一个位置
    35. permutation(chars, begin + 1);
    36. }
    37. }
    38. }
    39. }