Задача: 294. Flip Game II
Сложность: 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 {
    func canWin(_ currentState: String) -> Bool {
        var stateArray = Array(currentState)
        
        for i in 0..<(stateArray.count - 1) {
            if stateArray[i] == "+" && stateArray[i + 1] == "+" {
                stateArray[i] = "-"
                stateArray[i + 1] = "-"
                let newState = String(stateArray)
                
                if !canWin(newState) {
                    stateArray[i] = "+"
                    stateArray[i + 1] = "+"
                    return true
                }
                
                stateArray[i] = "+"
                stateArray[i + 1] = "+"
            }
        }
        
        return false
    }
}

Ставь 👍 и забирай 📚 Базу знаний