294. Flip Game II

leetcode medium

#array#csharp#leetcode#medium#queue#recursion#string

Task

Вы играете в игру Flip со своим другом.

Вам дана строка currentState, которая содержит только символы '+' и '-'. Вы и ваш друг по очереди переворачиваете две последовательные "++" в "--". Игра заканчивается, когда игрок больше не может сделать ход, и, следовательно, другой игрок становится победителем.

Верните true, если начальный игрок может гарантировать победу, и false в противном случае.

Пример:

Input: currentState = "++++"

Output: true

Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".

C# solution

matched/original

public class Solution {
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.Length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public bool CanWin(string currentState) {
        char[] stateArray = currentState.ToCharArray();
        
        for (int i = 0; i < stateArray.size() - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                string newState = new string(stateArray);
                
                if (!CanWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

Java solution

matched/original

public class Solution {
    public boolean canWin(String currentState) {
        char[] stateArray = currentState.toCharArray();
        
        for (int i = 0; i < stateArray.length - 1; i++) {
            if (stateArray[i] == '+' && stateArray[i + 1] == '+') {
                stateArray[i] = '-';
                stateArray[i + 1] = '-';
                String newState = new String(stateArray);
                
                if (!canWin(newState)) {
                    stateArray[i] = '+';
                    stateArray[i + 1] = '+';
                    return true;
                }
                
                stateArray[i] = '+';
                stateArray[i + 1] = '+';
            }
        }
        
        return false;
    }
}

JavaScript solution

matched/original

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;
    }
}

Python solution

matched/original

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

Go solution

matched/original

package main

func canWin(currentState string) bool {
  stateArray := []rune(currentState)
    
  for i := 0; i < len(stateArray)-1; i++ {
    if stateArray[i] == '+' && stateArray[i+1] == '+' {
      stateArray[i] = '-'
      stateArray[i+1] = '-'
      newState := string(stateArray)
            
      if !canWin(newState) {
        stateArray[i] = '+'
        stateArray[i+1] = '+'
        return true
      }
            
      stateArray[i] = '+'
      stateArray[i+1] = '+'
    }
  }
    
  return false
}

Explanation

Algorithm

Генерация всех возможных следующих ходов:

Для текущего состояния currentState, создайте все возможные новые состояния, заменяя каждую пару "++" на "--".

Рекурсивная проверка выигрыша:

Для каждого нового состояния вызовите функцию рекурсивно, чтобы проверить, может ли противник проиграть в этом новом состоянии.

Если противник не может сделать ход, верните true, так как начальный игрок гарантирует победу.

Проверка всех возможных ходов:

Если для всех возможных ходов начальный игрок не может гарантировать победу, верните false.

Иначе, если есть хотя бы один ход, при котором противник проигрывает, верните true.

😎