Задача: 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 {
    canWin(currentState) {
        let stateArray = currentState.split('');
        
        for (let i = 0; i < stateArray.length - 1; i++) {
            if (stateArray[i] === '+' && stateArray[i + 1] === '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                let newState = stateArray.join('');
                
                if (!this.canWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

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