LC.P1079[活字印刷]

方法一：计数+回溯

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 {
    int[] cnt = new int[26];

    public int numTilePossibilities(String tiles) {
        for (char c : tiles.toCharArray()) {
            ++cnt[c - 'A'];
        }
        return dfs();
    }

    private int dfs() {
        int ans = 0;
        for (int i = 0; i < cnt.length; ++i) {
            if (cnt[i] > 0) {
                ++ans;
                --cnt[i];
                ans += dfs();
                ++cnt[i];
            }
        }
        return ans;
    }
}
  • 时间复杂度：$O(n \times n!)$，其中$n$为字母种类数目
  • 空间复杂度：$O(n)$