LeetCode1079-活字印刷

发表于 | 分类于

题目链接

英文链接：https://leetcode.com/problems/letter-tile-possibilities/

中文链接：https://leetcode-cn.com/problems/letter-tile-possibilities/

题目详述

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

示例 1：

1
2
3
输入："AAB"
输出：8
解释：可能的序列为 "A", "B", "AA", "AB", "BA", "AAB", "ABA", "BAA"。

示例 2：

1
2
输入："AAABBC"
输出：188

提示：

  • 1 <= tiles.length <= 7
  • tiles 由大写英文字母组成

题目详解

  • LeetCode47-全排列II 是求所有不重复的全排列，可以在这个的基础上对非空子母序列进行计数。
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
33
34
35
public class LeetCode_01079 {

    public int numTilePossibilities(String tiles) {
        return dfs(tiles.toCharArray(), 0);
    }

    private int dfs(char[] cs, int s) {
        int res = 0;
        for (int i = s; i < cs.length; ++i) {
            if (isDuplicate(cs, s, i)) {
                continue;
            }
            ++res;
            swap(cs, s, i);
            res += dfs(cs, s + 1);
            swap(cs, s, i);
        }
        return res;
    }

    private boolean isDuplicate(char[] cs, int s, int e) {
        for (int i = s; i < e; ++i) {
            if (cs[i] == cs[e]) {
                return true;
            }
        }
        return false;
    }

    private void swap(char[] cs, int i, int j) {
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;
    }
}
  • 可以换一种方法进行回溯。先用一个哈希表统计各个字母出现的个数，然后依次分配。
  • 例如：对于输入 AAB。A = 2， B = 1。
  • 长度为 1 时，可以选择 A 或 B，于是有了 A，B。
  • 长度为 2 时
    • 对于 A
      • A = 1， B = 1。
      • 可以选择 A 或 B，于是有了 AA，AB。
    • 对于 B
      • A = 2， B = 0。
      • 只能选择 A，于是有了 BA。
  • 长度为 3 时
    • 对于 AA
      • A = 0， B = 1。
      • 只能选择 B，于是有了 AAB。
    • 对于 AB
      • A = 1， B = 0。
      • 只能选择 A，于是有了 ABA。
    • 对于 BA
      • A = 1， B = 0。
      • 只能选择 A，于是有了 BAA。
  • 所以对于输入 AAB，输出为 8，其他输入依此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class LeetCode_01079 {

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