跳转至

面试题 38. 字符串的排列

题目描述

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

 

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

 

示例:

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

 

限制：

1 <= s 的长度 <= 8

解法

方法一：回溯 + 哈希表

我们设计一个函数 $dfs(i)$，表示当前排列到了第 $i$ 个位置，我们需要在第 $i$ 个位置上填入一个字符，这个字符可以从 $s[i..n-1]$ 中任意选择。

函数 $dfs(i)$ 的执行过程如下：

  • 如果 $i = n-1$，说明当前排列已经填满，将当前排列加入答案，返回。
  • 否则，我们需要在 $s[i..n-1]$ 中选择一个字符填入第 $i$ 个位置，我们可以使用哈希表记录哪些字符已经被填过，从而避免重复填入相同的字符。
  • 在 $s[i..n-1]$ 中选择一个字符填入第 $i$ 个位置，然后递归执行函数 $dfs(i+1)$，即填入第 $i+1$ 个位置。
  • 回溯，撤销选择，即将第 $i$ 个位置的字符填回原位。

我们在主函数中调用函数 $dfs(0)$，即从第 0 个位置开始填入字符。最后返回答案数组即可。

时间复杂度 $O(n! \times n)$，空间复杂度 $O(n)$。其中 $n$ 是字符串 $s$ 的长度。需要进行 $n!$ 次排列，每次排列需要 $O(n)$ 的时间复制字符串。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution:
    def permutation(self, s: str) -> List[str]:
        def dfs(i):
            if i == len(s) - 1:
                ans.append(''.join(cs))
                return
            vis = set()
            for j in range(i, len(s)):
                if cs[j] not in vis:
                    vis.add(cs[j])
                    cs[i], cs[j] = cs[j], cs[i]
                    dfs(i + 1)
                    cs[i], cs[j] = cs[j], cs[i]

        ans = []
        cs = list(s)
        dfs(0)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    private List<String> ans = new ArrayList<>();
    private char[] cs;

    public String[] permutation(String s) {
        cs = s.toCharArray();
        dfs(0);
        return ans.toArray(new String[ans.size()]);
    }

    private void dfs(int i) {
        if (i == cs.length - 1) {
            ans.add(String.valueOf(cs));
            return;
        }
        Set<Character> vis = new HashSet<>();
        for (int j = i; j < cs.length; ++j) {
            if (vis.add(cs[j])) {
                swap(i, j);
                dfs(i + 1);
                swap(i, j);
            }
        }
    }

    private void swap(int i, int j) {
        char t = cs[i];
        cs[i] = cs[j];
        cs[j] = t;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<string> permutation(string s) {
        vector<string> ans;
        function<void(int)> dfs = [&](int i) {
            if (i == s.size() - 1) {
                ans.push_back(s);
                return;
            }
            unordered_set<char> vis;
            for (int j = i; j < s.size(); ++j) {
                if (!vis.count(s[j])) {
                    vis.insert(s[j]);
                    swap(s[i], s[j]);
                    dfs(i + 1);
                    swap(s[i], s[j]);
                }
            }
        };
        dfs(0);
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func permutation(s string) (ans []string) {
    cs := []byte(s)
    var dfs func(int)
    dfs = func(i int) {
        if i == len(s)-1 {
            ans = append(ans, string(cs))
            return
        }
        vis := map[byte]bool{}
        for j := i; j < len(s); j++ {
            if !vis[cs[j]] {
                vis[cs[j]] = true
                cs[i], cs[j] = cs[j], cs[i]
                dfs(i + 1)
                cs[i], cs[j] = cs[j], cs[i]
            }
        }
    }
    dfs(0)
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
function permutation(s: string): string[] {
    const n = s.length;
    const cs = s.split('');
    const set = new Set<string>();
    const dfs = (i: number) => {
        if (i === n) {
            set.add(cs.join(''));
            return;
        }
        dfs(i + 1);
        for (let j = i + 1; j < n; j++) {
            [cs[i], cs[j]] = [cs[j], cs[i]];
            dfs(i + 1);
            [cs[i], cs[j]] = [cs[j], cs[i]];
        }
    };
    dfs(0);
    return [...set];
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
use std::collections::HashSet;
impl Solution {
    fn dfs(i: usize, cs: &mut Vec<char>, res: &mut Vec<String>) {
        if i == cs.len() {
            res.push(cs.iter().collect());
            return;
        }
        let mut set = HashSet::new();
        for j in i..cs.len() {
            if set.contains(&cs[j]) {
                continue;
            }
            set.insert(cs[j]);
            cs.swap(i, j);
            Self::dfs(i + 1, cs, res);
            cs.swap(i, j);
        }
    }

    pub fn permutation(s: String) -> Vec<String> {
        let mut res = Vec::new();
        Self::dfs(0, &mut s.chars().collect(), &mut res);
        res
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * @param {string} s
 * @return {string[]}
 */
var permutation = function (s) {
    const cs = s.split('');
    const ans = [];
    const n = s.length;
    const dfs = i => {
        if (i == n - 1) {
            ans.push(cs.join(''));
            return;
        }
        const vis = new Set();
        for (let j = i; j < n; ++j) {
            if (!vis.has(cs[j])) {
                vis.add(cs[j]);
                [cs[i], cs[j]] = [cs[j], cs[i]];
                dfs(i + 1);
                [cs[i], cs[j]] = [cs[j], cs[i]];
            }
        }
    };
    dfs(0);
    return ans;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Solution {
    private char[] cs;
    private List<string> ans = new List<string>();

    public string[] Permutation(string s) {
        cs = s.ToCharArray();
        dfs(0);
        return ans.ToArray();
    }

    private void dfs(int i) {
        if (i == cs.Length - 1) {
            ans.Add(new string(cs));
            return;
        }
        var vis = new HashSet<char>();
        for (int j = i; j < cs.Length; ++j) {
            if (vis.Add(cs[j])) {
                (cs[i], cs[j]) = (cs[j], cs[i]);
                dfs(i + 1);
                (cs[i], cs[j]) = (cs[j], cs[i]);
            }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    private var ans: [String] = []
    private var cs: [Character] = []

    func permutation(_ s: String) -> [String] {
        cs = Array(s)
        dfs(0)
        return ans
    }

    private func dfs(_ i: Int) {
        if i == cs.count - 1 {
            ans.append(String(cs))
            return
        }
        var vis: Set<Character> = []
        for j in i..<cs.count {
            if !vis.contains(cs[j]) {
                vis.insert(cs[j])
                swap(i, j)
                dfs(i + 1)
                swap(i, j)
            }
        }
    }

    private func swap(_ i: Int, _ j: Int) {
        let t = cs[i]
        cs[i] = cs[j]
        cs[j] = t
    }
}

评论