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;
                
            }
        }
    }
    

  • 0
    H

    @tsar2512 there's more than x,y,z when you adding one more layer.


Log in to reply
 

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