Why this solution takes so long?


  • 0
    Q

    So I have tried two different approach, the first one is the normal backtracking solution, which takes 2ms.
    And I came up with the solution below.
    The idea is to get the result of one less pair of parentheses, then insert another into each possible location.

    public List<String> generateParenthesis(int n) {
        List<String> rt = new ArrayList();
        if(n == 0){
            rt.add("");
            return rt;
        }
        List<String> sub = generateParenthesis(n-1);
        for(String item : sub){
            for(int i = 0 ; i <= item.length() / 2; i++){
                // insert another pair
                String newStr = item.substring(0, i) +"()" + item.substring(i);
                if(!rt.contains(newStr)){
                    rt.add(newStr);
                }
            }
        }
        return rt;
    }
    

    This
    It took 25ms. Could anyone help me to understand what's the time complexity here?


Log in to reply
 

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