Anybody know the Time Complexity of the Recur Solution?


  • 0
    A

    This is the naive recursive solution, where generates all possible next moves, and do canWin() on all next moves, to see if any makes it.

    It seems horrendous in terms of performance, but miraculously it was accepted. Does anyone know what is the time complexity of this?

    public boolean canWin(String s) {
            if (s.isEmpty()) return false;
            
            // all next moves possible, and opponent must lose
            for (int i = 0; i < s.length()-1; i++) {
                if (s.substring(i, i+2).equals("++")) {
                    String nextMove = s.substring(0, i) + "--" + s.substring(i+2);
                    
                    boolean opponentLose = !canWin(nextMove);
                    if (opponentLose) return true;
                }
            }
            return false;
        }
    

  • 0

    I quote @jeantimex 's time complexity analysis.

    For the time complexity, here is what I thought, let's say the length of the input string s is n, there are at most n - 1 ways to replace "++" to "--" (imagine s is all "+++..."), once we replace one "++", there are at most (n - 2) - 1 ways to do the replacement, it's a little bit like solving the N-Queens problem, the time complexity is (n - 1) x (n - 3) x (n - 5) x ..., so it's O(n!!), double factorial.

    see https://discuss.leetcode.com/topic/27250/share-my-java-backtracking-solution


Log in to reply
 

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