Letter Tile Possibilities 活字印刷

问题描述：

你有一套活字字模 tiles，其中每个字模上都刻有一个字母 tiles[i]。返回你可以印出的非空字母序列的数目。

每个活字字模只能使用一次。

tiles.length范围[1,7]

都是大写字母

分析

这个问题规模不大最多就7个字符。
要求在给出的字模中拼出所有的非空字母序列的数目。
字模可以去百度一下，传统的印刷中用的是铅字模。
要求一个字模只能用一次，但是相同的字可能有多个字模可用。
然后就是拼，方向就是递归，字模数量为N，那么结果的字符串的长度就是1~N.
即从N个字模中，选出C个字符的排列。在此需要注意的是排列中重复的问题。
即字符A中2个字模A1，A2，最终只会有1个排列AA.
如果使用map统计配合递归，就不会有这个问题。
将每个字符的频次进行统计，然后定义dfs(map),表示剩余map中的字符可以得到的所有非空字母序列。
因为每一层dfs中，取的字符都不一样，所以剩余的map状态也不一样。
关键点在于dfs的意义，不同的返回值，内部处理也不一样。
每次从字符中选一个，剩余的字符继续dfs，dfs返回的是i-1个字符可以得到排列的数量。
这个比较容易理解，问题是什么时候结束的边界，同时还要解决不同长度的排列。
官解中的边界，为i=0,返回1，也就是说空字符串，也算一个排列。
这样对于单个字符B来说，就是返回2，表示字符串"B",“”,那么再加上之前的"A",可以得到"AB",“A”,为了保留1个"",所以官解上是以res=1进行初始化。

当然也可以用解决排列来处理
但是递归回溯的时间复杂度就非常高。

代码

回溯

class Solution {public int numTilePossibilities(String tiles) {Map<Character, Integer> count = new HashMap<>();for (char t : tiles.toCharArray()) {count.put(t, count.getOrDefault(t, 0) + 1);}Set<Character> tile = new HashSet<>(count.keySet());return dfs(tiles.length(), count, tile) - 1;}private int dfs(int i, Map<Character, Integer> count, Set<Character> tile) {if (i == 0) {return 1;}int res = 1;for (char t : tile) {if (count.get(t) > 0) {count.put(t, count.get(t) - 1);res += dfs(i - 1, count, tile);count.put(t, count.get(t) + 1);}}return res;}
}

时间复杂度 O(N*N!) 空间复杂度： O(N)

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;}
}

时间复杂度 O(N*N!) 空间复杂度： O(N)

2种DFS看着很相似，但是其意义却完全不同，所以内部的处理方式，结束边界，也完全不一样。第一个是官解的的dfs,可以理解为字符串长度为i时，可以得到的所有排列数，空字符也算一个。而第二个，可以理解为【以剩余cnt的字符可以得到所有的字符串排列数】。

其中包含了所有的排列，字符串长度从1~N，而官解的dfs，还多了一个空字符串。

动态规划

以DP的角度思考排列，实际上就是将M个字符选出N个可以得到的排列。

直接定义f[i] [j] 表示使用前i种字符，可以得到字符串长度=j的数量。

$\sum_{k=0}^{min(j,cnt)}{f[i-1][j-k]\times{j \choose k }}$
对于第i个字符，数量有cnt个，那么k==0，说明没使用第i个字符 $f [i] [j] = f [i - 1] [j]$ .

如果k=1,说明使用了1个， $f [i] [j] = f [i - 1] [j - 1] * j$ .

如果k=2,说明使用了2个， $f [i] [j] = f [i - 1] [j - 1] * j (j - 1)$ .

所以 $f [i] [j]$ 是一个累加的数据.

M 是字符的种类，j表示字符串的长度
$\sum_{j=1}^{n}{f[M][j]}即所求$

class Solution {private static final int MX = 8;private static final int[][] c = new int[MX][MX];static {for (int i = 0; i < MX; i++) {c[i][0] = c[i][i] = 1;for (int j = 1; j < i; j++)c[i][j] = c[i - 1][j - 1] + c[i - 1][j]; // 预处理组合数}}public int numTilePossibilities(String tiles) {var counts = new HashMap<Character, Integer>(); // 统计每个字母的出现次数for (var c : tiles.toCharArray())counts.merge(c, 1, Integer::sum); // counts[c]++int m = counts.size(), n = tiles.length();var f = new int[m + 1][n + 1];f[0][0] = 1; // 构造空序列的方案数int i = 1;for (var cnt : counts.values()) { // 枚举第 i 种字母for (int j = 0; j <= n; j++) // 枚举序列长度 jfor (int k = 0; k <= j && k <= cnt; k++) // 枚举第 i 种字母选了 k 个f[i][j] += f[i - 1][j - k] * c[j][k];i++;}int ans = 0;for (int j = 1; j <= n; j++)ans += f[m][j];return ans;}
}