字符串的排列

力扣剑指 Offer 38. 字符串的排列

题目说明

输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
限制：

1 <= s 的长度 <= 8

示例

1 2	输入：s = "abc" 输出：["abc","acb","bac","bca","cab","cba"]

笔者理解

此题是一道DFS算法问题，在力扣题库中被定义为中等题。

解法

当笔者阅读完此题后，发现此题是比较经典的DFS题目，让我们来看看具体如何实现的吧。

实现

class Solution {
    /*
     * DFS
     */

    List<String> list;

    public String[] permutation(String s) {
        int size = s.length();

        list = new ArrayList<String>();

        char[] ch = s.toCharArray();

        // 深度优先遍历
        dfs(ch, 0);

        // 动态数组转静态数组
        return list.toArray(new String[list.size()]);
    }

    public void dfs(char[] ch, int tick) {
        // 组建成功一个字符串
        if (tick == ch.length) {
            // 将字节数组作为参数创建字符串
            list.add(new String(ch));
            return;
        }

        for (int i = tick; i < ch.length; i++) {
            boolean temp = true;
            for (int j = tick; j < i; j++) {
                // 字母相同时，后面的组合相同，剪枝
                if (ch[i] == ch[j]) {
                    temp = false;
                }
            }
            if (temp) {
                // 交换两数
                char tempCh = ch[tick];
                ch[tick] = ch[i];
                ch[i] = tempCh;

                dfs(ch, tick + 1);

                // 复原两数
                tempCh = ch[tick];
                ch[tick] = ch[i];
                ch[i] = tempCh;
            }
        }
    }
}