2021/2/14 剑指 Offer 38. 字符串的排列

题目描述

输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例

输入

s = "abc"

返回值

["abc","acb","bac","bca","cab","cba"]

解题思路

1. 使用回溯法，逐层固定一个字母。
   
2. 可以用 Set 进行剪枝，去掉重复元素。规则是同一层内出现了一样的元素，则跳过。
   

Java代码实现

class Solution {
    ArrayList<String> list = new ArrayList<String>();
    char[] c;
    public String[] permutation(String s) {
        c = s.toCharArray();
        func(0);
        return list.toArray(new String[list.size()]);
    }

    public void func(int index) {
        if (index == c.length - 1) list.add(String.valueOf(c));
        HashSet<Character> set = new HashSet<Character>();
        for (int i = index; i < c.length; ++i) {
            if (set.contains(c[i])) continue;
            set.add(c[i]);
            switchPos(i, index);
            func(index + 1);
            switchPos(i, index);
        }
    }

    public void switchPos(int a, int b) {
        char temp = c[a];
        c[a] = c[b];
        c[b] = temp;
    }
}