1
\$\begingroup\$

For a leetcode problem to generate the valid parentheses of length 2n, I have written this solution. It is working for smaller inputs but not for larger inputs. Please suggest a way to optimise my code.

I have read the Stack Overflow questions but was unable to implement the same concept in my code.

 //I have writte a bruteforce approch and got all the possible combinations..
//Then filter all the combinations to check if every one of them is a valid combination



public class Solution {



    public ArrayList<String> generateParenthesis(int a) {

        ArrayList<String> allCombinations = getAllPossibleCombinations(2*a,new ArrayList<String>());
        ArrayList<String> prunedCombinations = new ArrayList<String>(); 

        for(String comb : allCombinations)
        {
            if(isCombinationValid(comb))
            {
                prunedCombinations.add(comb);
            }
        }

        return prunedCombinations;
    }

    //Bruteforce way to get all the combinations...
    public ArrayList<String> getAllPossibleCombinations(int num,ArrayList<String> presentCombinations)
    {
        //templist is used to populate the result and pass the values
        ArrayList<String> tempList = new ArrayList<String>();
        if(num == 0) //num is zero, so return the combinations
        {
            return presentCombinations;
        }
        else
        {
            //In first call, just add ( and )
            if(presentCombinations.isEmpty())
            {
                tempList.add("(");
                tempList.add(")");
            }
            else //From second call, add ( and ) for current values in stack
            {
                for(String presentComb : presentCombinations)
                {
                    tempList.add(presentComb+"(");
                    tempList.add(presentComb+")");
                }
            }
        }
        //To pass the intermediate values and num-1
       return getAllPossibleCombinations(num-1,tempList);
    }


    //Check if an individual combination is valid..
    //Use stack to match the paranthesis
    public boolean isCombinationValid(String comb)
    {
            Stack<Character> st = new Stack<Character>();

            for(int i=0 ; i < comb.length() ; i++)
            {
                char current = comb.charAt(i);
                if(current == '(')
                {
                    st.push('(');
                }
                else
                {
                    if(!st.isEmpty() && st.peek() == '(')
                    {
                        st.pop();
                    }
                    else
                    {
                        st.push(')');
                    }
                }
            }

            if(st.isEmpty())
            {
                return true;
            }
            else
            {
                return false;
            }

    }


}
\$\endgroup\$
1
  • \$\begingroup\$ Just stick like glue to the definition of well-formed parentheses expression (empty, prefixed, suffixed, surrounded) and use StringBuilder. \$\endgroup\$
    – greybeard
    Jan 5, 2016 at 3:49

1 Answer 1

1
\$\begingroup\$

isCombinationValid

          for(int i=0 ; i < comb.length() ; i++)
          {
              char current = comb.charAt(i);

Since you never use i for anything other than generating current, you could just

          for (char current : comb.toCharArray())
          {

This way you wouldn't have to manage i at all.

        if(st.isEmpty())
        {
            return true;
        }
        else
        {
            return false;
        }

This is more complicated than need be.

        return st.isEmpty();

This has the same result in seven fewer lines.

            if(current == '(')
            {
                st.push('(');
            }
            else
            {
                if(!st.isEmpty() && st.peek() == '(')
                {
                    st.pop();
                }
                else
                {
                    st.push(')');
                }
            }

Instead, you can say

            if (current == '(')
            {
                st.push('(');
            }
            else if (st.isEmpty())
            {
                return false;
            }
            else
            {
                st.pop();
            }

You know that anything in the stack must be a '(', so you don't need to peek to check. And if you ever find an extra ')', you can quit immediately. You already know that it's not well-formed. So if the first character is a ')', you don't even have to go through the rest of the string.

I prefer not to use an else with an if !. I just find the logic easier to follow this way. And I switched to the more common else if rather than

getAllPossibleCombinations

        if (presentCombinations.isEmpty())
        {
            temp.add("(");
            temp.add(")");
        }
        else //From second call, add ( and ) for current values in stack
        {

You are doing this with each recursive call, but that's not necessary. Rather than do this in getAllPossibleCombinations, replace

        ArrayList<String> allCombinations = getAllPossibleCombinations(2*a,new ArrayList<String>());
        ArrayList<String> prunedCombinations = new ArrayList<String>(); 
        for(String comb : allCombinations)

with

        List<String> initialCombinations = new ArrayList<>();
        initialCombinations.add("(");

        List<String> prunedCombinations = new ArrayList<>(); 
        for (String comb : getAllPossibleCombinations(2*a, initialCombinations)))

You don't need the ")" one at all, because no valid version can start with a closing parenthesis.

I also changed your use of ArrayList<String> as the variable type to just use List<String>. Unless you use some functionality specific to ArrayList, it is generally better to use the interface (List) rather than the implementation (ArrayList) as the type. This makes it easier to change the implementation in the future.

I also changed the right hand side to use the newer <> notation. It's possible that your Java doesn't support that. If so, just leave it as <String>.

One might argue that this makes getAllPossibleCombinations less reusable, as you have to pass a specific opening parameter. This is true, but it was also true of your original. To get around this, you can specify a version that does not require a List to be passed:

    public List<String> getAllPossibleCombinations(int maximumPairCount) {
        List<String> initialCombinations = new ArrayList<>();
        initialCombinations.add("(");

        return getAllPossibleCombinations(maximumPairCount - 1, initialCombinations);
    }

Now you could declare the two parameter version private, as all consumers should call this version instead. And you can get rid of your isEmpty check, as it will never be called that way. This won't shorten your code, but it will make it run faster, as you save checking isEmpty for nearly every call.

Optimization

The code that you link checks for validity as it builds the string. If you do that, you don't have to save invalid combinations like "))))". Since there are \$2^{2*n}\$ combinations but only a smaller number of these are valid, this should make your program take longer to run out of memory.

Note that if you do this, you don't return false if the stack has extra '(' in it. It's valid for a partial expression to have unmatched '('. What's invalid is unmatched ')'.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.