2026 华为OD机试真题 4月29日华为OD上机新系统考试真题 200 分题型

点击查看华为 OD 机试真题完整目录：2026最新华为OD机试新系统卷 + 双机位C卷 真题题库目录｜全覆盖题库 + 逐点算法考点详解

题目描述

在一个创意设计工坊中，设计师希望用不同的大写字母瓷砖拼出独特图案，给定一个只包含大写英文字母的图案字符串 LL ，要求你给出对 LL 重新排列的所有不相同的图案，但是有以下约束条件：

1. 相同的字母不能相邻

输入描述

• 输入一个长度不超过 1212 的字符串 LL ，确保都是大写的

输出描述

• 输出满足约束条件的L重新排列的所有不相同的排列数

示例1

输入

"AAB"

输出

1

说明

只有"ABAABA"满足条件

示例2

输入

""

输出

1

说明

空也是符合没有相邻的要求

示例3

输入

"AA"

输出

说明

AA 是相邻的，所以没有满足条件的

解题思路

核心思想

本题要求计算一个给定大写字母字符串的所有不重复全排列数，约束条件是：相同的字母不能相邻。

1. 全排列问题：这是一个典型的排列组合问题，可以使用回溯算法（DFS）来搜索所有可能的排列。
2. 去重处理：由于输入的字符串中可能包含重复的字母（如 "AAB"），为了避免统计重复的排列，我们需要：
   • 对输入字符串进行排序，使得相同的字符相邻。
   • 在回溯过程中，如果当前字符与前一个字符相同，且前一个字符在当前层级还未被使用过，则跳过当前字符（剪枝）。
3. 相邻约束：在回溯过程中，维护一个变量 lastChar 记录上一个放置的字符。如果当前尝试放置的字符与 lastChar 相同，则不符合条件，跳过。
4. 特殊情况：题目说明空字符串也符合要求（不相邻），应返回 1。

复杂度分析

• 时间复杂度：$O(N! \cdot N)$，其中 $N$ 是字符串长度（最大为 12）。最坏情况下（所有字符互不相同）全排列数为 $N!$。由于 $12! = 479,001,600$，在带有强力剪枝（相邻约束和字符去重）的情况下，实际搜索空间会大大减小。
• 空间复杂度：$O(N)$，用于递归调用的深度以及存储字符数组和标记数组。