Valid Parentheses problem, why is my code slow?
metodi022
63

I'm using Java to solve the valid parentheses problem. So, here is what I did:

Basic Cases:

  1. Check if input is empty, in this case, return empty string.
  2. Otherwise, if input is only 1 character, return it.
  3. Otherwise, if input is 2 character, check if they are equal and return empty string, otherwise, return the string.

Complicated case (if not in basic case, i.e., input is longer than 2 characters):

  1. Check if the first 2 characters are equal. If it is true, iterate on the substring of the string without the first 2 characters.
  2. Otherwise, if the first character form the input is a closing bracket, return it + iteration from the substring of the string without the 1st character
  3. Otherwise, execture the function match, witch tries to match the open parenthesis.

.

The function match works as follows:

  • Given the first character of the string and the rest of the substring (without the 1st character), iterate from the beginning on the substring and see if the result matches the given first character.

So, to get a boolean, I just run the function on the string and compare if the output is an empty string.

Example: solve ([]) -> match ( []) -> solve []) -> solve ) -> ) -> match () -> ""
.
Example: solve (({})()) -> 1. match ( ({})()) -> solve ({})()) -> 2. match ( {})()) -> solve {})()) -> solve )()) -> ) + solve ()) -> ) + solve ) -> ) + ) -> )) -> 2. match ()) -> 2. match ) -> ) -> 1. match () -> ""

.
Why is the code so slow? It says it runs 12ms and is only faster than 6% of other submissions.
Thanks for the help, here is the code:

class Solution {

    public String solve(String string)
    {
        if (string.equals(""))
        {
            return "";
        }
        else if (string.length() == 1)
        {
            return string;
        }
        else if (string.length() == 2)
        {
            if (test(string.charAt(0), string.charAt(1)))
            {
                return "";
            }
            else
            {
                return string;
            }
        }
        else
        {
            if (test(string.charAt(0), string.charAt(1)))
            {
                return solve(string.substring(2));
            }
            else
            {
                if (isClosing(string.charAt(0)))
                {
                    return string.charAt(0)+solve(string.substring(1));
                }
                else
                {
                    return match(string.charAt(0), string.substring(1));
                }
            }
        }
    }
    
    public String match(char element, String string)
    {
        String result = solve(string);
        
        if (result.equals(""))
        {
            return ""+element;
        }
        else if (test(element,result.charAt(0)))
        {
            if (result.length() > 1)
            {
                return result.substring(1);
            }
            else
            {
                return "";
            }
        }
        else
        {
            return string;
        }
    }
    
    public boolean test(char element1, char element2)
    {
        if (element1 == '(')
        {
            return (element2 == ')');
        }
        else if (element1 == '{')
        {
            return (element2 == '}');
        }
        else if (element1 == '[')
        {
            return (element2 == ']');
        }
        else
        {
            return false;
        }
    }
    
    public boolean isClosing(char element)
    {
        return (element == ')') || (element == '}') || (element == ']');
    }
    
    public boolean isValid(String s) {
        return (("").equals(solve(s)));
    }
}
Comments (1)