本问题对应的 leetcode 原文链接：剑指 Offer 38. 字符串的排列

问题描述

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

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

示例:

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

限制：

1 <= s 的长度 <= 8

解题思路

视频讲解直达： 本题视频讲解

代码实现

class Solution {
    List<Character> path;
    List<String> res;
    boolean[] visited;
    public String[] permutation(String s) {
        this.path = new ArrayList<>();
        this.res = new ArrayList<>();
        this.visited = new boolean[s.length()];

        char[] arr = s.toCharArray();
        Arrays.sort(arr);
        dfs(arr, 0);

        String[] ss = new String[res.size()];
        for(int i = 0; i < res.size(); i++){
            ss[i] = res.get(i);
        }

        return ss;

    }
    // 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
    void dfs(char[] arr, int k){
        if(arr.length == k){
           res.add(listToString(path));
           return;
        }

        //进行N叉树搜索
        for(int i = 0; i < arr.length; i++){
            // 剪枝 aab
            if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
                continue;
            }
            if(visited[i] == false){
                // 递归访问
                visited[i] = true;
                path.add(arr[i]);
                dfs(arr, k + 1);
                path.remove(path.size() - 1);
                visited[i] = false;
            }
        }
    }

    String listToString(List<Character> list){
        StringBuilder b = new StringBuilder();
        for(int i = 0; i < list.size(); i++){
            b.append(list.get(i));
        }

        return b.toString();
    }
}

时间复杂度：O(n!n)
空间复杂度：O(n^2)

Python

class Solution(object):
    def permutation(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        path = []
        res = []
        visited = [False] * len(s)

        arr = sorted(list(s))

        def dfs(k):
            if k == len(arr):
                res.append("".join(path))
                return

            for i in range(len(arr)):
                if i > 0 and arr[i] == arr[i - 1] and not visited[i - 1]:
                    continue
                if not visited[i]:
                    visited[i] = True
                    path.append(arr[i])
                    dfs(k + 1)
                    path.pop()
                    visited[i] = False

        dfs(0)

        return res

C++

class Solution {
public:
    vector<string> permutation(string s) {
        vector<char> path;
        vector<string> res;
        vector<bool> visited(s.size(), false);

        sort(s.begin(), s.end());

        function<void(int)> dfs = [&](int k) {
            if (k == s.size()) {
                res.push_back(string(path.begin(), path.end()));
                return;
            }

            for (int i = 0; i < s.size(); i++) {
                if (i > 0 && s[i] == s[i - 1] && !visited[i - 1]) {
                    continue;
                }
                if (!visited[i]) {
                    visited[i] = true;
                    path.push_back(s[i]);
                    dfs(k + 1);
                    path.pop_back();
                    visited[i] = false;
                }
            }
        };

        dfs(0);

        return res;
    }
};

Go

func permutation(s string) []string {
    var path []rune
    var res []string
    visited := make([]bool, len(s))

    runes := []rune(s)
    sort.Slice(runes, func(i, j int) bool {return runes[i] < runes[j]})

    var dfs func(int)
    dfs = func(k int) {
        if k == len(runes) {
            res = append(res, string(path))
            return
        }

        for i := 0; i < len(runes); i++ {
            if i > 0 && runes[i] == runes[i-1] && !visited[i-1] {
                continue
            }
            if !visited[i] {
                visited[i] = true
                path = append(path, runes[i])
                dfs(k+1)
                path = path[:len(path)-1]
                visited[i] = false
            }
        }
    }

    dfs(0)

    return res
}

JS

/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function(s) {
  var path = [];
  var res = [];
  var visited = new Array(s.length).fill(false);

  var arr = s.split("");
  arr.sort();
  dfs(arr, 0);

  var ss = new Array(res.length);
  for (var i = 0; i < res.length; i++) {
    ss[i] = res[i];
  }

  return ss;

  function dfs(arr, k) {
    if (arr.length === k) {
      res.push(listToString(path));
      return;
    }

    for (var i = 0; i < arr.length; i++) {
      if (i > 0 && arr[i] === arr[i - 1] && visited[i - 1] === false) {
        continue;
      }
      if (visited[i] === false) {
        visited[i] = true;
        path.push(arr[i]);
        dfs(arr, k + 1);
        path.pop();
        visited[i] = false;
      }
    }
  }

  function listToString(list) {
    var b = "";
    for (var i = 0; i < list.length; i++) {
      b += list[i];
    }

    return b;
  }
};

shuaidi永久会员

收藏 海报挣佣金 推广链接