剑指offer最优解Java版-字符串的排列

题目描述

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

解决方法

回溯法图解：

java-full-permutation.png

public class Solution {
    public static ArrayList<String> Permutation(String str) {
        List<String> resultList = new ArrayList<>();
        if (str.length() == 0)
            return (ArrayList) resultList;
        //递归的初始值为（str数组，空的list，初始下标0）
        fun(str.toCharArray(), resultList, 0);
        Collections.sort(resultList);
        return (ArrayList) resultList;
    }

    private static void fun(char[] ch, List<String> list, int i) {
        //这是递归的终止条件，就是i下标已经移到char数组的末尾的时候，考虑添加这一组字符串进入结果集中
        if (i == ch.length - 1) {
            //判断一下是否重复
            if (!list.contains(new String(ch))) {
                list.add(new String(ch));
                return;
            }
        } else {
            // 这一段是回溯法
            for (int j = i; j < ch.length; j++) {
                swap(ch, i, j);
                fun(ch, list, i + 1);
                swap(ch, i, j);
            }
        }
    }

    //交换数组的两个下标的元素
    private static void swap(char[] str, int i, int j) {
        if (i != j) {
            char t = str[i];
            str[i] = str[j];
            str[j] = t;
        }
    }

    public static void main(String[] args) {
        System.out.println(Permutation("abc"));
    }
}

复杂度分析：

• 时间复杂度：O(n!)。
• 空间复杂度：O(n!)。

哎呀，如果我的名片丢了。微信搜索“全菜工程师小辉”，依然可以找到我