LeetCode 面试题 08.08. 有重复字符串的排列组合 中等

作者:Choi Yang

更新于:6 个月前

字数统计:431 字

阅读时长:2 分钟

阅读量:

题目描述

有重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合。

示例 1:

 输入：S = "qqe"
 输出：["eqq","qeq","qqe"]

示例 2:

 输入：S = "ab"
 输出：["ab", "ba"]

提示:

字符都是英文字母。
字符串长度在[1, 9]之间。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/permutation-ii-lcci 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

全排列，直接用回溯法即可，数据量比较小，暴力完事~

javascript

var permutation = function (S) {
  let res = new Set();
  let vis = [];
  let dfs = (t) => {
    if (t.length === S.length) return res.add(t);
    for (let i = 0; i < S.length; i++) {
      if (vis[i]) continue;
      vis[i] = true;
      dfs(t + S[i]);
      vis[i] = false;
    }
  };
  dfs("");
  return [...res];
};

cpp

class Solution {
public:
    vector<string> permutation(string S) {
        set<string> res;
        vector<bool> vis(S.size(), false);
        dfs(S, "", res, vis);
        return vector<string>(res.begin(), res.end());
    }

    void dfs(string s, string t, set<string>& res, vector<bool>& vis) {
        if (t.size() == s.size()) {
            res.insert(t);
            return;
        }
        for (int i = 0; i < s.size(); i++) {
            if (vis[i]) continue;
            vis[i] = true;
            dfs(s, t + s[i], res, vis);
            vis[i] = false;
        }
    }
};

java

class Solution {
    public String[] permutation(String S) {
        Set<String> res = new HashSet<>();
        boolean[] vis = new boolean[S.length()];
        dfs(S, "", res, vis);
        return res.toArray(new String[0]);
    }

    private void dfs(String s, String t, Set<String> res, boolean[] vis) {
        if (t.length() == s.length()) {
            res.add(t);
            return;
        }
        for (int i = 0; i < s.length(); i++) {
            if (vis[i]) continue;
            vis[i] = true;
            dfs(s, t + s.charAt(i), res, vis);
            vis[i] = false;
        }
    }
}

python

class Solution:
    def permutation(self, S: str) -> List[str]:
        res = set()
        vis = [False] * len(S)

        def dfs(t):
            if len(t) == len(S):
                res.add(t)
                return
            for i in range(len(S)):
                if vis[i]:
                    continue
                vis[i] = True
                dfs(t + S[i])
                vis[i] = False

        dfs("")
        return list(res)

学如逆水行舟，不进则退

Contributors

Choi Yang