题目描述

剑指 Offer 38. 字符串的排列

难度中等237收藏分享切换为英文接收动态反馈

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

测试用例

• 功能测试（输入的字符串中有一个或者多个字符）
• 特殊输入测试（输入的字符串的内容为空或者空指针）

题目考点

• 考察应聘者的思维能力。
• 考察应聘者对递归的理解和编程能力。

解题思路

通过将字符串分成两部分，从而把大问题分解成小问题，然后使用递归解决。

1. 求所有可能出现在第一位置的字符，即把第一个字符和后面所有的字符交换。(记得为了下一次的交换，要把之前交换的东西交换回来)
2. 固定第一个字符，求后面所有字符的排列。
3. 这时候我们仍把后面的所有字符分成两个部分：后面字符的第一个字符，以及这个字符之后的所有字符。重复过程1，2。

参考解题

class Solution {
   
    List<String> res = new LinkedList<>();
    char[] c;
    public String[] permutation(String s) {
   
        c = s.toCharArray();
        dfs(0);
        return res.toArray(new String[res.size()]);
    }
    void dfs(int x) {
   
        if(x == c.length - 1) {
   
            res.add(String.valueOf(c));      // 添加排列方案
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for(int i = x; i < c.length; i++) {
   
            if(set.contains(c[i])) continue; // 重复，因此剪枝
            set.add(c[i]);
            swap(i, x);                      // 交换，将 c[i] 固定在第 x 位
            dfs(x + 1);                      // 开启固定第 x + 1 位字符
            swap(i, x);                      // 恢复交换
        }
    }
    void swap(int a, int b) {
   
        char tmp = c[a];
        c[a] = c[b];
        c[b] = tmp;
    }
}