今日题目

https://leetcode.com/problems/letter-tile-possibilities/description/

解题思路

本题要求统计能够生成多少种不同的字母序列。

方法

因此，我们可以使用回溯法枚举所有可能的方案。

复杂度

  • 时间复杂度： $O(2^N)$，N 为序列的长度。

  • 空间复杂度： $O(N)$，N 为序列的长度。

代码

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        counter = defaultdict(int)
        for ch in tiles:
            counter[ch] += 1

        def dfs(counter):
            total = 0
            for ch in counter:
                if counter[ch] == 0:
                    continue
                # Choose character
                total += 1
                counter[ch] -= 1
                total += dfs(counter)
                counter[ch] += 1  # backtracking
            return total
        return dfs(counter)