Dynamic Programming Solution, why is it wrong? Is there an issue with testing?


  • 0
    T

    I submitted this code for the generate parentheses problem. It is failing in testcase with input 4. I do not understand, what is wrong with the approach. I have checked the solutions, so I understand how to solve the problem, but this seems like a correct approach as well.

    I am basically starting with 1 giving simple (), and then concatenating paranthesis around the previous result, or alternatively before and after (if they are not the same).

    public class Solution {
            
        public List<String> generateParenthesis(int n){
            if(n<1){
                //manage possible error conditions
                return new ArrayList<String>();
            }
            if(n==1){
                    List<String> temp = new ArrayList<String>();
                    temp.add(new String("()"));
                    mem.put(n,temp);
                    return temp;
            }else{
                    List<String> temp = generateParenthesis(n-1);
                    List<String> output = new ArrayList<String>();
                    
                    for(int i= 0; i < temp.size(); i++){
                        //there are two options for each element in the returned list
                        String s = temp.get(i);
                        String x = "(" + s + ")";
                        String y = "()" + s;
                        String z = s + "()";
                        
                        output.add(x);
                        output.add(y);
                        if(y.compareTo(z)!=0)
                            output.add(z);
                    }
            
                    return output;
                
            }
        }
    }
    

Log in to reply
 

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