README.md

面试题 08.07. 无重复字符串的排列组合

English Version

题目描述

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。

示例1:

 输入：S = "qwe"
 输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

示例2:

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

提示:

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

解法

方法一：回溯

class Solution:
    def permutation(self, S: str) -> List[str]:
        def dfs(u, t):
            if u == n:
                ans.append(''.join(t))
                return
            for i in range(n):
                if vis[i]:
                    continue
                vis[i] = True
                t.append(S[i])
                dfs(u + 1, t)
                t.pop()
                vis[i] = False

        n = len(S)
        vis = [False] * n
        ans = []
        dfs(0, [])
        return ans

class Solution {
    public String[] permutation(String S) {
        Set<Character> vis = new HashSet<>();
        List<String> ans = new ArrayList<>();
        StringBuilder t = new StringBuilder();
        dfs(0, S, t, ans, vis);
        return ans.toArray(new String[0]);
    }

    private void dfs(int u, String S, StringBuilder t, List<String> ans, Set<Character> vis) {
        if (u == S.length()) {
            ans.add(t.toString());
            return;
        }
        for (char c : S.toCharArray()) {
            if (vis.contains(c)) {
                continue;
            }
            vis.add(c);
            t.append(c);
            dfs(u + 1, S, t, ans, vis);
            t.deleteCharAt(t.length() - 1);
            vis.remove(c);
        }
    }
}

class Solution {
public:
    vector<string> permutation(string S) {
        unordered_set<char> vis;
        vector<string> ans;
        string t = "";
        dfs(0, S, t, ans, vis);
        return ans;
    }

    void dfs(int u, string& S, string& t, vector<string>& ans, unordered_set<char>& vis) {
        if (u == S.size()) {
            ans.push_back(t);
            return;
        }
        for (char& c : S) {
            if (vis.count(c)) continue;
            vis.insert(c);
            t.push_back(c);
            dfs(u + 1, S, t, ans, vis);
            vis.erase(c);
            t.pop_back();
        }
    }
};

func permutation(S string) []string {
	vis := make(map[byte]bool)
	var ans []string
	var t []byte
	var dfs func(u int, t []byte)
	dfs = func(u int, t []byte) {
		if u == len(S) {
			ans = append(ans, string(t))
			return
		}
		for i := range S {
			if vis[S[i]] {
				continue
			}
			vis[S[i]] = true
			t = append(t, S[i])
			dfs(u+1, t)
			vis[S[i]] = false
			t = t[:len(t)-1]
		}
	}
	dfs(0, t)
	return ans
}

/**
 * @param {string} S
 * @return {string[]}
 */
var permutation = function (S) {
    let res = [];
    let arr = [...S];
    let prev = [];
    let record = new Array(S.length).fill(false);
    dfs(arr, 0, prev, record, res);
    return res;
};

function dfs(arr, depth, prev, record, res) {
    if (depth == arr.length) {
        res.push(prev.join(''));
        return;
    }
    for (let i = 0; i < arr.length; i++) {
        if (record[i]) {
            continue;
        }
        prev.push(arr[i]);
        record[i] = true;
        dfs(arr, depth + 1, prev, record, res);
        prev.pop();
        record[i] = false;
    }
}