Сложность: medium
Вы играете в игру Flip со своим другом.
Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.
Верните true, если начальный игрок может гарантировать победу, и false в противном случае.
Пример:
Input: currentState = "++++"
Output: true
Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".
👨💻 Алгоритм:
1⃣Генерация всех возможных следующих ходов:
Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".
2⃣Рекурсивная проверка выигрыша:
Для каждого нового состояния вызовите функцию рекурсивно, чтобы проверить, может ли противник проиграть в этом новом состоянии.
Если противник не может сделать ход, верните true, так как начальный игрок гарантирует победу.
3⃣Проверка всех возможных ходов:
Если для всех возможных ходов начальный игрок не может гарантировать победу, верните false.
Иначе, если есть хотя бы один ход, при котором противник проигрывает, верните true.
😎 Решение:
class Solution:
def canWin(self, currentState: str) -> bool:
stateArray = list(currentState)
for i in range(len(stateArray) - 1):
if stateArray[i] == '+' and stateArray[i + 1] == '+':
stateArray[i] = '-'
stateArray[i + 1] = '-'
newState = ''.join(stateArray)
if not self.canWin(newState):
stateArray[i] = '+'
stateArray[i + 1] = '+'
return True
stateArray[i] = '+'
stateArray[i + 1] = '+'
return False
Ставь 👍 и забирай 📚 Базу знаний