Medium

题目描述

你有 n 个瓷砖，每个瓷砖上都印有一个字母 tiles[i]。

返回你可以用这些瓷砖印出的非空字母序列的数量。

示例 1：

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

示例 2：

输入：tiles = "AAABBC"
输出：188

示例 3：

输入：tiles = "V"
输出：1

约束条件：

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

提示：

  • 尝试使用回溯 DFS 来构建字符串，考虑在每个位置可以放置什么。

解题思路

这是一个典型的回溯算法问题，需要统计所有可能的排列组合数量。

核心思路：

  1. 字符计数：首先统计每个字符的出现次数，这样可以处理重复字符的情况
  2. 回溯生成：使用DFS回溯算法，在每个位置尝试放置每种可用的字符
  3. 去重处理：通过字符计数的方式天然避免了重复序列的生成

算法步骤：

  • 统计输入字符串中每个字符的频次
  • 使用回溯函数，对于每个长度的序列（1到n），尝试所有可能的字符组合
  • 在放置字符时，减少该字符的可用数量；回溯时恢复
  • 累计所有可能的序列数量

两种实现思路：

  1. 直接回溯：每次尝试所有剩余字符，用数组记录字符使用情况
  2. 计数回溯：先统计字符频次，回溯时基于频次进行选择（推荐，更高效）

时间复杂度相对较低，因为题目限制了字符串长度最大为7。

代码实现

class Solution {
public:
    int numTilePossibilities(string tiles) {
        unordered_map<char, int> count;
        for (char c : tiles) {
            count[c]++;
        }
        return dfs(count);
    }
    
private:
    int dfs(unordered_map<char, int>& count) {
        int sum = 0;
        for (auto& [c, cnt] : count) {
            if (cnt > 0) {
                count[c]--;
                sum += 1 + dfs(count);
                count[c]++;
            }
        }
        return sum;
    }
};

class Solution:
    def numTilePossibilities(self, tiles: str) -> int:
        from collections import Counter
        
        def dfs(count):
            total = 0
            for char in count:
                if count[char] > 0:
                    count[char] -= 1
                    total += 1 + dfs(count)
                    count[char] += 1
            return total
        
        count = Counter(tiles)
        return dfs(count)

public class Solution {
    public int NumTilePossibilities(string tiles) {
        var count = new Dictionary<char, int>();
        foreach (char c in tiles) {
            count[c] = count.GetValueOrDefault(c, 0) + 1;
        }
        return Dfs(count);
    }
    
    private int Dfs(Dictionary<char, int> count) {
        int sum = 0;
        foreach (var kvp in count.ToList()) {
            char c = kvp.Key;
            int cnt = kvp.Value;
            if (cnt > 0) {
                count[c]--;
                sum += 1 + Dfs(count);
                count[c]++;
            }
        }
        return sum;
    }
}

var numTilePossibilities = function(tiles) {
    const count = {};
    for (let c of tiles) {
        count[c] = (count[c] || 0) + 1;
    }
    
    function dfs(count) {
        let sum = 0;
        for (let c in count) {
            if (count[c] > 0) {
                count[c]--;
                sum += 1 + dfs(count);
                count[c]++;
            }
        }
        return sum;
    }
    
    return dfs(count);
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(∑(n!/(n₁!×n₂!×…×nₖ!))) 其中n是字符串长度，nᵢ是第i种字符的数量。最坏情况约O(8^7)
空间复杂度O(k + 递归深度) 其中k是不同字符的数量，递归深度最大为n