)
获取大写字母瓷砖拼出独特图案数量
2026 华为OD机试真题 4月29日华为OD上机新系统考试真题 200 分题型
点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解
题目描述
在一个创意设计工坊中，设计师希望用不同的大写字母瓷砖拼出独特图案，给定一个只包含大写英文字母的图案字符串 LL，要求你给出对 LL重新排列的所有不相同的图案，但是有以下约束条件：
- 相同的字母不能相邻
2026 华为OD机试真题 4月29日华为OD上机新系统考试真题 200 分题型
输入描述
- 输入一个长度不超过 1212 的字符串 LL，确保都是大写的
输出描述
- 输出满足约束条件的L重新排列的所有不相同的排列数
示例1
输入
"AAB"输出
1说明
只有"ABAABA"满足条件
示例2
输入
""输出
1说明
空也是符合没有相邻的要求
示例3
输入
"AA"输出
0说明
AA是相邻的，所以没有满足条件的
解题思路
核心思想
本题要求计算一个给定大写字母字符串的所有不重复全排列数，约束条件是：相同的字母不能相邻。
- 全排列问题：这是一个典型的排列组合问题，可以使用回溯算法（DFS）来搜索所有可能的排列。
- 去重处理：由于输入的字符串中可能包含重复的字母（如 "AAB"），为了避免统计重复的排列，我们需要： - 对输入字符串进行排序，使得相同的字符相邻。 - 在回溯过程中，如果当前字符与前一个字符相同，且前一个字符在当前层级还未被使用过，则跳过当前字符（剪枝）。
- 相邻约束：在回溯过程中，维护一个变量
lastChar记录上一个放置的字符。如果当前尝试放置的字符与lastChar相同，则不符合条件，跳过。 - 特殊情况：题目说明空字符串也符合要求（不相邻），应返回 1。
复杂度分析
- 时间复杂度：$O(N! \cdot N)$，其中 $N$ 是字符串长度（最大为 12）。最坏情况下（所有字符互不相同）全排列数为 $N!$。由于 $12! = 479,001,600$，在带有强力剪枝（相邻约束和字符去重）的情况下，实际搜索空间会大大减小。
- 空间复杂度：$O(N)$，用于递归调用的深度以及存储字符数组和标记