LeetCode Problem 2038: 如果相邻两个颜色均相同则删除当前颜色 (Winner of the Game)

在本篇博客中，我们将深入探讨 LeetCode 第2038题——如果相邻两个颜色均相同则删除当前颜色。该问题涉及字符串处理与游戏策略，旨在考察如何在给定规则下判断游戏的胜负。我们将详细解析问题、探索解决方案，并通过代码示例展示如何实现这一逻辑。

问题描述

背景

给定一个由 'A' 和 'B' 组成的字符串 colors，每个字符代表一个颜色片段。Alice 和 Bob 在玩一个游戏，他们轮流从字符串中删除颜色。Alice 先手。

游戏规则

1. 删除规则：

   • Alice 可以删除一个 'A'，条件是该 'A' 的相邻两个颜色片段也都是 'A'。
   • Bob 可以删除一个 'B'，条件是该 'B' 的相邻两个颜色片段也都是 'B'。

2. 限制：

   • 无法删除位于字符串两端的颜色片段，因为它们没有两个相邻的颜色片段。
   • 每次删除一个颜色片段后，字符串会重新连接，新的相邻关系会重新建立。

3. 胜负判定：

   • 如果一方无法进行删除操作，则该玩家输掉游戏，另一方获胜。
   • 假设 Alice 和 Bob 都采用最优策略，判断 Alice 是否获胜。

示例

示例 1

输入: colors = "AAABABB"
输出: true
解释:
- Alice 删除中间的 'A'，字符串变为 "AABABB"。
- Bob 无法进行删除操作，因为没有三个连续的 'B'。
- Alice 获胜。

示例 2

输入: colors = "AA"
输出: false
解释:
- Alice 无法进行删除操作，因为字符串长度不足。
- Bob 获胜。

示例 3

输入: colors = "ABBBBBBBAAA"
输出: false
解释:
- Alice 删除最后的 'A'，字符串变为 "ABBBBBBBAA"。
- Bob 删除一个 'B'，字符串变为 "ABBBBBBAA"。
- Alice 无法进行删除操作。
- Bob 获胜。

提示

• 1 <= colors.length <= 10^5
• colors 只包含字母 'A' 和 'B'

解决方案

要判断 Alice 是否能获胜，我们需要计算 Alice 和 Bob 各自能进行多少次删除操作，然后比较两者的次数。

关键观察

1. 连续字符的分组：对于连续的 'A' 或 'B'，计算其长度。
2. 可删除次数：对于每一组连续的字符，只有当长度大于等于3时，才能进行删除操作。具体的删除次数为 长度 - 2。
   • 例如，连续5个 'A'，Alice 可以进行 5 - 2 = 3 次删除。
3. 总删除次数：
   • Alice 的总删除次数为所有连续 'A' 组的 (长度 - 2) 之和。
   • Bob 的总删除次数为所有连续 'B' 组的 (长度 - 2) 之和。
4. 胜负判定：如果 Alice 的删除次数大于 Bob 的删除次数，则 Alice 获胜，返回 true；否则，返回 false。

算法步骤

1. 初始化两个计数器 alice_moves 和 bob_moves 分别记录 Alice 和 Bob 的可删除次数。
2. 遍历字符串 colors，统计连续 'A' 和 'B' 的长度。
3. 对于每个连续的 'A' 或 'B' 组，计算其可删除次数，并累加到相应的计数器。
4. 最后比较 alice_moves 和 bob_moves 的值，判断 Alice 是否获胜。

复杂度分析

• 时间复杂度：O(n)，其中 n 是字符串 colors 的长度。我们只需遍历一次字符串。
• 空间复杂度：O(1)，仅使用了常数级别的额外空间。

代码实现

以下是基于上述思路的 Python 实现：

class Solution:
    def winnerOfGame(self, colors: str) -> bool:
        alice_moves = 0
        bob_moves = 0
        n = len(colors)
        i = 0
        
        while i < n:
            current_char = colors[i]
            count = 1
            # 统计当前字符连续出现的次数
            while i + 1 < n and colors[i + 1] == current_char:
                count += 1
                i += 1
            # 如果连续字符数大于等于3，计算可删除次数
            if count >= 3:
                if current_char == 'A':
                    alice_moves += count - 2
                else:
                    bob_moves += count - 2
            i += 1
        
        # Alice 必须有比 Bob 更多的删除次数才能获胜
        return alice_moves > bob_moves

代码解析

1. 初始化：

   alice_moves = 0
   bob_moves = 0
   n = len(colors)
   i = 0
   

   • alice_moves 和 bob_moves 分别记录 Alice 和 Bob 的可删除次数。
   • n 是字符串的长度，i 是当前遍历的索引。

2. 遍历字符串：

   while i < n:
       current_char = colors[i]
       count = 1
       # 统计当前字符连续出现的次数
       while i + 1 < n and colors[i + 1] == current_char:
           count += 1
           i += 1
       # 如果连续字符数大于等于3，计算可删除次数
       if count >= 3:
           if current_char == 'A':
               alice_moves += count - 2
           else:
               bob_moves += count - 2
       i += 1
   

   • 对于每一个字符，统计其连续出现的次数 count。
   • 如果 count >= 3，则根据字符类型增加相应的删除次数。
   • 最后，移动到下一个不同的字符。

3. 胜负判断：

   return alice_moves > bob_moves
   

   • 如果 Alice 的删除次数大于 Bob 的，则 Alice 获胜，返回 true；否则，返回 false。

示例运行

让我们通过几个示例来验证我们的算法。

示例 1

colors = "AAABABB"
solution = Solution()
print(solution.winnerOfGame(colors))  # 输出: True

解析：

• 连续 'A' 的组：'AAA'，可删除次数为 3 - 2 = 1。
• 连续 'B' 的组：'B'、'BB'，均不足3个，不可删除。
• Alice 的删除次数 1，Bob 的删除次数 0。
• 因为 1 > 0，Alice 获胜。

示例 2

colors = "AA"
solution = Solution()
print(solution.winnerOfGame(colors))  # 输出: False

解析：

• 连续 'A' 的组：'AA'，不足3个，不可删除。
• Alice 的删除次数 0，Bob 的删除次数 0。
• 因为 0 不是大于 0，Alice 无法获胜。

示例 3

colors = "ABBBBBBBAAA"
solution = Solution()
print(solution.winnerOfGame(colors))  # 输出: False

解析：

• 连续 'A' 的组：'A'、'AAA'，可删除次数为 1。
• 连续 'B' 的组：'BBBBBBB'，可删除次数为 7 - 2 = 5。
• Alice 的删除次数 1，Bob 的删除次数 5。
• 因为 1 小于 5，Bob 获胜。

总结

我们了解到如何通过统计连续字符的数量来判断 Alice 和 Bob 各自的删除次数。关键在于识别连续的 'A' 和 'B' 组，并根据规则计算可删除次数。最终，通过比较两者的删除次数，我们可以高效地判断游戏的胜负。