活字印刷 图解题解

这道题到底在问什么

输入

tiles = "AAB"

输出

8 （A, B, AA, AB, BA, AAB, ABA, BAA）

输入

tiles = "V"

输出

1 （只有 "V" 一种）

最优解：一步一步想明白

1. 3记住这套「挑一个就算一种、走到头收回换下一个、相同字母只挑一次」，下面每一帧都在套它。
2. 4上面一排是三个字模 A、A、B（已经排好序），下面 path 是正在拼的序列，右边收集每一种印出来的序列。规矩：每层挑一个没用过的字模接到 path 末尾，接出一个就算印出一种。
3. 5挑第 0 个字模 A，接到末尾，拼出序列 "A"。每拼出一个非空序列就算印出一种，答案加到 1。
4. 6挑第 1 个字模 A，接到末尾，拼出序列 "AA"。每拼出一个非空序列就算印出一种，答案加到 2。
5. 7挑第 2 个字模 B，接到末尾，拼出序列 "AAB"。每拼出一个非空序列就算印出一种，答案加到 3。
6. 8"AAB" 这条已经拼满、把末尾的 B 收回来，path 退回 "AA"，回上一层换下一个字模。
7. 9"AA" 这条能接的都试过了，把末尾的 A 收回来，path 退回 "A"，回上一层换下一个字模。
8. 10挑第 2 个字模 B，接到末尾，拼出序列 "AB"。每拼出一个非空序列就算印出一种，答案加到 4。
9. 11挑第 1 个字模 A，接到末尾，拼出序列 "ABA"。每拼出一个非空序列就算印出一种，答案加到 5。
10. 12"ABA" 这条已经拼满、把末尾的 A 收回来，path 退回 "AB"，回上一层换下一个字模。
11. 13"AB" 这条能接的都试过了，把末尾的 B 收回来，path 退回 "A"，回上一层换下一个字模。
12. 14"A" 这条能接的都试过了，把末尾的 A 收回来，path 退回 空，回上一层换下一个字模。
13. 15这一层又遇到字母 A，它和前一个 A 一样、而且前一个这层还没挑，选它拼出来的序列会和刚才那条重复，跳过去重。
14. 16挑第 2 个字模 B，接到末尾，拼出序列 "B"。每拼出一个非空序列就算印出一种，答案加到 6。
15. 17挑第 0 个字模 A，接到末尾，拼出序列 "BA"。每拼出一个非空序列就算印出一种，答案加到 7。
16. 18挑第 1 个字模 A，接到末尾，拼出序列 "BAA"。每拼出一个非空序列就算印出一种，答案加到 8。
17. 19"BAA" 这条已经拼满、把末尾的 A 收回来，path 退回 "BA"，回上一层换下一个字模。
18. 20"BA" 这条能接的都试过了，把末尾的 A 收回来，path 退回 "B"，回上一层换下一个字模。
19. 21这一层又遇到字母 A，它和前一个 A 一样、而且前一个这层还没挑，选它拼出来的序列会和刚才那条重复，跳过去重。
20. 22"B" 这条能接的都试过了，把末尾的 B 收回来，path 退回 空，回上一层换下一个字模。
21. 23三个字模的所有挑法都搜遍了，右边正好攒了 8 种不同的非空序列：A、AA、AAB、AB、ABA、B、BA、BAA。所以 "AAB" 的答案就是 8。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        def dfs(cnt: Counter) -> int:
            ans = 0
            for i, x in cnt.items():
                if x > 0:
                    ans += 1
                    cnt[i] -= 1
                    ans += dfs(cnt)
                    cnt[i] += 1
            return ans

        cnt = Counter(tiles)
        return dfs(cnt)

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numTilePossibilities(string tiles) {
        int cnt[26]{};
        for (char c : tiles) {
            ++cnt[c - 'A'];
        }
        function<int(int* cnt)> dfs = [&](int* cnt) -> int {
            int res = 0;
            for (int i = 0; i < 26; ++i) {
                if (cnt[i] > 0) {
                    ++res;
                    --cnt[i];
                    res += dfs(cnt);
                    ++cnt[i];
                }
            }
            return res;
        };
        return dfs(cnt);
    }
};

import java.util.*;
class Solution {
    public int numTilePossibilities(String tiles) {
        int[] cnt = new int[26];
        for (char c : tiles.toCharArray()) {
            ++cnt[c - 'A'];
        }
        return dfs(cnt);
    }

    private int dfs(int[] cnt) {
        int res = 0;
        for (int i = 0; i < cnt.length; ++i) {
            if (cnt[i] > 0) {
                ++res;
                --cnt[i];
                res += dfs(cnt);
                ++cnt[i];
            }
        }
        return res;
    }
}

复杂度

面试官可能追问