1079.活字印刷

链接：1079.活字印刷
难度：Medium
标签：哈希表、字符串、回溯、计数
简介：你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

题解 1 - cpp

• 编辑时间：2023-05-19
• 执行用时：144ms
• 内存消耗：22.7MB
• 编程语言：cpp
• 解法介绍：全排列。

class Solution {
public:
    int numTilePossibilities(string tiles) {
        unordered_set<string> s;
        unordered_set<int> idxs;
        function<void(string)> dfs = [&](string cur) {
            s.insert(cur);
            if (cur.size() == tiles.size()) return;
            for (int i = 0; i < tiles.size(); i++) {
                if (idxs.count(i)) continue;
                idxs.insert(i);
                dfs(cur + tiles[i]);
                idxs.erase(i);
            }
        };
        dfs("");
        return s.size() - 1;
    }
};

题解 2 - python

• 编辑时间：2023-05-19
• 执行用时：204ms
• 内存消耗：24.8MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        s = set()
        idxs = set()
        def dfs(cur: str):
            s.add(cur)
            if len(cur) == len(tiles):
                return
            for i in range(len(tiles)):
                if i in idxs:
                    continue
                idxs.add(i)
                dfs(cur + tiles[i])
                idxs.remove(i)
        dfs('')
        return len(s) - 1

题解 3 - rust

• 编辑时间：2023-05-19
• 执行用时：40ms
• 内存消耗：3MB
• 编程语言：rust
• 解法介绍：同上。

impl Solution {
    pub fn num_tile_possibilities(tiles: String) -> i32 {
        use std::collections::HashSet;
        let tiles = tiles.as_bytes().iter().map(|v| *v).collect::<Vec<u8>>();
        let mut s = HashSet::<String>::new();
        let mut idxs = HashSet::<usize>::new();
        fn dfs(
            s: &mut HashSet<String>,
            idxs: &mut HashSet<usize>,
            tiles: &Vec<u8>,
            cur: &mut Vec<u8>,
        ) {
            s.insert(String::from_utf8(cur.clone()).unwrap());
            if cur.len() != tiles.len() {
                for i in 0..tiles.len() {
                    if !idxs.contains(&i) {
                        idxs.insert(i);
                        cur.push(tiles[i]);
                        dfs(s, idxs, tiles, cur);
                        cur.pop();
                        idxs.remove(&i);
                    }
                }
            }
        }
        let mut cur: Vec<u8> = vec![];
        dfs(&mut s, &mut idxs, &tiles, &mut cur);
        (s.len() - 1) as i32
    }
}