Categorías
Algorithms

LeetCode – Flip Game II (Java)

Estás jugando al siguiente juego del tirón con tu amigo: Dada una cadena que contiene solo estos dos caracteres: + y -, tú y tu amigo se turnan para convertir dos «++» consecutivos en «-«. El juego termina cuando una persona ya no puede hacer un movimiento y, por lo tanto, la otra persona será la ganadora.

Escribe una función para determinar si el jugador inicial puede garantizar una victoria.

Por ejemplo, dado s = «++++», devuelve verdadero. El jugador inicial puede garantizar una victoria cambiando el «++» del medio para que se convierta en «+ – +».

Solución Java

Este problema se resuelve retrocediendo.

public boolean canWin(String s) {
    if(s==null||s.length()==0){
        return false;
    }
 
   return canWinHelper(s.toCharArray()); 
}
 
public boolean canWinHelper(char[] arr){
    for(int i=0; i<arr.length-1;i++){
        if(arr[i]=='+'&&arr[i+1]=='+'){
            arr[i]='-';
            arr[i+1]='-';
 
            boolean win = canWinHelper(arr);
 
            arr[i]='+';
            arr[i+1]='+';
 
            //if there is a flip which makes the other player lose, the first play wins
            if(!win){
                return true;
            }
        }
    }
 
    return false;
}

Complejidad del tiempo

Aproximadamente, el tiempo es n * n * … n, que es O (n ^ n). La razón es que cada recursión toma O (n) y hay totalmente n recursiones.

Por Programación.Click

Más de 20 años programando en diferentes lenguajes de programación. Apasionado del code clean y el terminar lo que se empieza. ¿Programamos de verdad?

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *