遊戲互動題 移除顏色相同的字卡 Leetcode #2038

這題的題目在這裡

題目敘述

題目會給定我們一個輸入陣列，裡面的字母A和字母B分別代表兩種顏色的卡片。

假如某張卡片的左右都是相同的，例如AAA，Alice可以抽掉中間那張A。

同樣的，假如某張卡片的左右都是相同的，例如BBB，Bob可以抽掉中間那張B。

請問Alice和Bob輪流玩抽卡遊戲，每回合都用最優解的方式去玩。Alice和Bob輪流各抽一張卡片，Alice先手。
假如輪到某個回合，已經無法再抽出卡牌，則當下這個玩家就輸了。

請問最後是誰贏?
如果Alice贏的話回傳True，如果是Bob贏回傳False。

測試範例

Example 1:

Input: colors = "AAABABB"
Output: true
Explanation:
AAABABB -> AABABB
Alice moves first.
She removes the second 'A' from the left since that is the only 'A' whose neighbors are both 'A'.

Now it's Bob's turn.
Bob cannot make a move on his turn since there are no 'B's whose neighbors are both 'B'.
Thus, Alice wins, so return true.

Example 2:

Input: colors = "AA"
Output: false
Explanation:
Alice has her turn first.
There are only two 'A's and both are on the edge of the line, so she cannot move on her turn.
Thus, Bob wins, so return false.

Example 3:

Input: colors = "ABBBBBBBAAA"
Output: false
Explanation:
ABBBBBBBAAA -> ABBBBBBBAA
Alice moves first.
Her only option is to remove the second to last 'A' from the right.

ABBBBBBBAA -> ABBBBBBAA
Next is Bob's turn.
He has many options for which 'B' piece to remove. He can pick any.

On Alice's second turn, she has no more pieces that she can remove.
Thus, Bob wins, so return false.

約束條件

Constraints:

• 1 <= colors.length <= 105
• colors consists of only the letters 'A' and 'B'

演算法

其實仔細模擬幾個範例之後可以發現，Alice和Bob的局面在開局後就固定下來，勝負已知，而且彼此的操作不影響對方。

為什麼?

下文中的'這著記號只是為了向讀者說明抽了哪張卡片，其實還是原本的顏色。

比如說
AA'ABBBAA
這局Alice抽掉左方的A'之後變成

AABB'BAA
這局再換Bob抽掉中間的B'，之後變成

AABBAA
此時Alice 無法再操作，判定Bob獲勝。Bob上一局也無法讓Alice左右兩側的AA和AA互相串連成更大一組的AAAA。

其他的例子也是，開局時的A、B分布已經固定，之後兩個玩家的操作已經無法改變局面。

關鍵就在於AAA和BBB總共有多少個，如果AAA的數目比BBB還多，那麼Alice最後必勝。反之，就是Bob必勝。

程式碼

class Solution:
　def winnerOfGame(self, colors: str) -> bool:
　　
　　n = len(colors)

　　# number of pieces alice can take
　　# number of pieces bob bob can take
　　alice, bob = 0, 0

　　for i in range(1, n-1):

　　　if colors[i-1] == colors[i] and colors[i] == colors[i+1]:

　　　　if colors[i] == "A":
　　　　　alice += 1
　　　　
　　　　else:
　　　　　bob += 1

　　# Judge whether Alice can win or not
　　return alice > bob
　　　

複雜度分析

時間複雜度:

O( n ) 從左到右掃描一次，掃描並且計算AAA和BBB的總數目。

空間複雜度:

O(1) 只有使用固定的臨時變數，所耗費的記憶體空間為常數級別O(1)

關鍵知識點

這題的關鍵在於先模擬幾個小範例，發現局面在開局已經固定，勝負已分，之後的抽卡操作並不影響勝負局面。

關鍵在於AAA和BBB的總數。

如果 AAA的數目 > BBB的數目，代表Alice每次可以從AAA抽走一張A，相對的Bob能抽B的次數比較少，兩人輪流，一定是Bob先走到死局，所以Alice必勝。

有點類似腦筋急轉彎的題目，如果太早落入一定要使用DP動態規劃，或者Greedy貪心法的先入為主刻板印象，反而落入陷阱。

Reference:

[1] Python O(n) by pattern scan - Remove Colored Pieces if Both Neighbors are the Same Color - LeetCode