Simple backtracking inspired by Flip Game I


  • 23
    S
    public boolean canWin(String s) {
        List<String> list = new ArrayList<>();
        for(int i = 0; i < s.length() - 1; i++){
            if(s.charAt(i) == '+' && s.charAt(i + 1) == '+')
                list.add(s.substring(0, i) + "--" + s.substring(i + 2, s.length()));         // generate all possible sequence after every attempt
        }
        /*if(list.isEmpty())
            return false;*/
        for(String str : list){
            if(!canWin(str))             // if there is any one way the next player can't win, take it and you'll win
                return true;
        }
        return false;      
    }

  • 0

    Why the

    if(list.isEmpty())
        return false;
    

    ?


  • 0
    S

    In that case the player couldn't make any move....so he lost


  • 0

    Yes, but why do you have that code? It's unnecessary.


  • 0
    S

    Aha, you are right!


  • 0

    Ok :-). I had btw speed-tested it, in case you were doing it as optimization, and there was no significant difference (2-3% faster, I think).

    How about separating it into two functions, one being the unchanged original one for Flip Game I function? I think that would make your separation idea even clearer and would look really good.

    public boolean canWin(String s) {
        for (String next : generatePossibleNextMoves(s))
            if(!canWin(next))
                return true;
        return false;      
    }

  • 0

    What the ...? I speed-tested that function-separated version to see how much slower it is, and... it's a lot faster! Averages about 250 ms, compared to around 320 ms for your all-in-one version. I'm baffled.


  • 0
    5

    Hi Stefan, we do you think is the complexity of this implementation?


  • 0

    Gotta be something exponential. If you start with "+" * 2n, then the search will at least come across the 2n strings built just from "++" and "--", i.e., where every odd-index characters is the same as the character before it.


  • 0
    D

    I use the exactly same solution as you. but we can add hashmap to memo tested strings which reduces the running time to 24ms


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.