算法笔记_025:字符串的全排列（Java）

描述

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

SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

解决方案

递归实现

从字符串中选出一个字符作为排列的第一个字符，然后对剩余的字符进行全排列。如此递归处理，从而得到所有字符的全排列。

/*
     * 参数arrayA:给定字符串的字符数组 参数start:开始遍历字符与其后面各个字符将要进行交换的位置 参数end:字符串数组的最后一位
     * 函数功能：输出字符串数字的各个字符全排列
     */
    public void recursionArrange(char[] arrayA, int start, int end) {
        if (end < 1)
            return;
        if (start == end) {
            System.out.println(String.valueOf(arrayA));
        } else {
            for (int i = start; i <= end; i++) {
                swap(arrayA, i, start);
                recursionArrange(arrayA, start + 1, end);
                swap(arrayA, i, start);
            }
        }

    }

    // 交换数组m位置和n位置上的值
    public void swap(char[] arrayA, int m, int n) {
        if (m == n) {
            return;
        }
        char temp = arrayA[m];
        arrayA[m] = arrayA[n];
        arrayA[n] = temp;
    }

    public static void main(String[] args) {
        StringTest test = new StringTest();
        String A = "abc";
        char[] arrayA = A.toCharArray();
        test.recursionArrange(arrayA, 0, arrayA.length - 1);
    }

 

扫码关注我们
微信号：SRE实战
拒绝背锅 运筹帷幄