题解 | 字符串的排列

1、解题思路

1. 回溯法： 使用回溯法生成所有可能的排列。在递归过程中，使用标记数组 visited 来记录哪些字符已经被使用过，避免重复使用。为了避免重复的排列，在每一层递归中跳过与前一个字符相同且未被使用的字符。时间复杂度：O(n!)，空间复杂度：O(n!)（存储结果的空间）。
2. 库函数法： 使用语言内置的库函数（如 Python 的 itertools.permutations）直接生成所有排列，然后去重。简单但不符合面试要求。

2、代码实现

C++

#include <string>
#include <vector>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串vector
     */
    vector<string> Permutation(string str) {
        // write code here
        vector<string> result;
        if (str.empty()) {
            result.push_back("");
            return result;
        }
        sort(str.begin(), str.end());
        vector<bool> visited(str.size(), false);
        string path;
        backtrack(str, path, visited, result);
        return result;
    }

    void backtrack(const string& str, string& path, vector<bool>& visited,
                   vector<string>& result) {
        if (path.size() == str.size()) {
            result.push_back(path);
            return ;
        }
        for (int i = 0; i < str.size(); ++i) {
            if (visited[i] || (i > 0 && str[i] == str[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.push_back(str[i]);
            backtrack(str, path, visited, result);
            path.pop_back();
            visited[i] = false;
        }
    }
};

Java

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串ArrayList
     */
    public ArrayList<String> Permutation (String str) {
        // write code here
        ArrayList<String> result = new ArrayList<>();
        if (str == null || str.length() == 0) {
            result.add("");
            return result;
        }
        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        boolean[] visited = new boolean[chars.length];
        backtrack(chars, new StringBuilder(), visited, result);
        return result;
    }

    private void backtrack(char[] chars, StringBuilder path, boolean[] visited,
                           ArrayList<String> result) {
        if (path.length() == chars.length) {
            result.add(path.toString());
            return;
        }
        for (int i = 0; i < chars.length; ++i) {
            if (visited[i] || (i > 0 && chars[i] == chars[i - 1] && !visited[i - 1])) {
                continue;
            }
            visited[i] = true;
            path.append(chars[i]);
            backtrack(chars, path, visited, result);
            path.deleteCharAt(path.length() - 1);
            visited[i] = false;
        }
    }
}

Python

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param str string字符串 
# @return string字符串一维数组
#
class Solution:
    def Permutation(self , str: str) -> List[str]:
        # write code here
        result = []
        if not str:
            return [""]
        str = sorted(str)
        visited = [False] * len(str)
        self.backtrack(str, [], visited, result)
        return result

    def backtrack(self, str, path, visited, result):
        if len(path) == len(str):
            result.append(''.join(path))
            return
        for i in range(len(str)):
            if visited[i] or (i > 0 and str[i] == str[i - 1] and not visited[i - 1]):
                continue
            visited[i] = True
            path.append(str[i])
            self.backtrack(str, path, visited, result)
            path.pop()
            visited[i] = False

3、复杂度分析

1. 排序： 首先对字符串进行排序，这样可以方便地跳过重复字符。
2. 回溯法： 使用标记数组 visited 来记录哪些字符已经被使用过。在递归过程中，跳过与前一个字符相同且未被使用的字符，以避免重复的排列。
3. 效率： 时间复杂度：O(n!)，因为需要生成所有可能的排列。空间复杂度：O(n!)，用于存储所有排列结果。