解题思路
题目要求在 N 个卡片组中各选一张卡片,按组号顺序拼成一个长度为 N 的字母序列,且序列中不能出现相同字母。需要统计所有不同的合法序列个数。
由于 N≤6,每组卡片数不超过 8,总搜索空间很小,可以使用深度优先搜索(DFS)回溯枚举所有可能的序列,并通过以下两点保证正确性:
- 字符互不相同:搜索过程中维护一个计数数组(或哈希表)
used,记录当前路径上每个字母是否已被使用。只有当前卡片上的字母未被使用时,才允许将其加入序列,并继续向下一组搜索。
- 序列不重复:由于同一组内可能有重复字母(例如字符串
"aab"),直接枚举会生成多条相同的序列。为了避免重复计数,需要将所有构造出的序列存入一个集合 seen 中(如哈希集合),最后以集合的大小作为答案。也可以在每组内部先对字符去重,但全局去重更加通用。