剑指Offer系列（java版，详细解析）38.字符串的排列

淡淡的烟草味﹌ 2022-10-22 07:41 93阅读 0赞

# 题目描述 #

#### [剑指 Offer 38. 字符串的排列][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;
        }
    }

[Offer 38.]: https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/