[Leetcode 1079] Letter Tile Possibilities

原题说明

You have a set of tiles, where each tile has one letter tiles[i] printed on it. Return the number of possible non-empty sequences of letters you can make.

Example 1:

Input: “AAB”
Output: 8
Explanation: The possible sequences are “A”, “B”, “AA”, “AB”, “BA”, “AAB”, “ABA”, “BAA”.

Example 2:

Input: “AAABBC”
Output: 188

Note:

1 <= tiles.length <= 7
tiles consists of uppercase English letters.

解题思路

采用递归的方式。用一个长度为26的vector<int> ch_count来记录当前剩余的每一个字母及对应的个数。
在递归函数dfsCount中，用int count表示当前ch_count能够组成的序列数，
遍历ch_count，每一个对应个数不为零的字母可以加入组合中，count++，对应的字母个数减一，然后调用递归函数。
调用完毕后，不要忘记backtracing，对应字母的个数应当恢复原样（加一）。

示例代码 (cpp)

class Solution {
    int dfsCount(vector<int>& ch_count) {
        int count = 0;
        for (int i = 0; i < ch_count.size(); ++i) {
            if (ch_count[i] == 0) {
                continue;
            }
            ++count;
            ch_count[i]--;
            count += dfsCount(ch_count);
            ch_count[i]++;
        }
        return count;
    }
public:
    int numTilePossibilities(string tiles) {
        vector<int> ch_count(26, 0);
        for (const auto tile : tiles) {
            ch_count[tile - 'A']++;
        }
        return dfsCount(ch_count);
    }
};

示例代码 (java)

class Solution {
    public int numTilePossibilities(String tiles) {
        int[] count = new int[26];
        for (char c : tiles.toCharArray()) count[c - 'A']++;
        return dfs(count);
    }
    
    int dfs(int[] arr) {
        int sum = 0;
        for (int i = 0; i < 26; i++) {
            if (arr[i] == 0) continue;
            sum++;
            arr[i]--;
            sum += dfs(arr);
            arr[i]++;
        }
        return sum;
    }
}

示例代码 (python)

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        freq = collections.Counter(tiles)
        prod = 1
        for f in freq.values():
            prod *= f + 1
        res = 0
        for i in range(1, prod):
            digits = []
            for f in freq.values():
                digits.append(i % (f + 1))
                i = i // (f + 1)
            tmp = math.factorial(sum(digits))
            for d in digits:
                tmp //= math.factorial(d)
            res += tmp
        return res

复杂度分析

时间复杂度: O(26^N), N为tiles的长度
空间复杂度: O(1), 栈的深度为O(N)

视频讲解

我们在Youtube上更新了视频讲解，欢迎关注！