微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 剑指offer 38.字符串的排列

剑指offer 38.字符串的排列

题目描述

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

题解

(回溯) O(n! * n)

和 46. 全排列 的唯一区别就是这道题目存在重复答案，所以需要去重，去重的思路首先将数组排序，让相同的数相邻，如果当前数等于前一个数且前一个数没有被使用过，则跳过当前数，继续查找下一个要放在当前位置上的数，始终保证排列后的序列相同数的相对顺序不变。

扩展题目：46. 全排列

时间复杂度

全排列总共有 A^n_n 种方案，即 n!，记录每种方案需要 O(n) 的时间，所以总时间复杂度为 O(n!*n)。

空间复杂度

额外空间复杂度 O(n)

C++ 代码

class Solution {
public:
    vector<string> res;
    string path;
    vector<bool> st;

    void dfs(int u, string& s) {
        if (u == s.size()) {
            res.push_back(path);
            return;
        }

        for (int i = 0; i < s.size(); i ++ ) {
            // 如果当前数等于前一个数且前一个数没用过，则使用前一个数
            if (i && !st[i - 1] && s[i - 1] == s[i]) continue;
            if (!st[i]) {
                path += s[i];
                st[i] = true;
                dfs(u + 1, s);
                st[i] = false;
                path.pop_back();
            }
        }
    }

    vector<string> permutation(string s) {
        sort(s.begin(), s.end());
        st = vector<bool>(s.size());
        dfs(0, s);
        return res;
    }
};

Java 代码

import java.util.*;

public class Solution {
    public String[] permutation(String s) {
        char[] charArray = s.toCharArray();
        Arrays.sort(charArray);
        String sortedStr = new String(charArray);

        List<String> res = new ArrayList<>();
        boolean[] st = new boolean[s.length()];
        dfs(0, sortedStr, st, new StringBuilder(), res);

        return res.toArray(new String[0]);
    }

    private void dfs(int u, String s, boolean[] st, StringBuilder path, List<String> res) {
        if (u == s.length()) {
            res.add(path.toString());
            return;
        }

        for (int i = 0; i < s.length(); i ++ ) {
            // 如果当前数等于前一个数且前一个数没用过，则使用前一个数
            if (i > 0 && !st[i - 1] && s.charAt(i - 1) == s.charAt(i)) continue;
            if (!st[i]) {
                path.append(s.charAt(i));
                st[i] = true;
                dfs(u + 1, s, st, path, res);
                st[i] = false;
                path.deleteCharAt(path.length() - 1);
            }
        }
    }
}

Python 代码

class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(u, s, st, path, res):
            if u == len(s):
                res.append(''.join(path))
                return

            for i in range(len(s)):
                # 如果当前数等于前一个数且前一个数没用过，则使用前一个数
                if i > 0 and not st[i - 1] and s[i - 1] == s[i]:
                    continue
                if not st[i]:
                    path.append(s[i])
                    st[i] = True
                    dfs(u + 1, s, st, path, res)
                    st[i] = False
                    path.pop()

        s = sorted(s)
        res = []
        path = []
        st = [False] * len(s)
        dfs(0, s, st, [], res)
        
        return res

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer