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.