Short, Easy to Follow 8ms Java Solution


  • 20
    L
    public class Solution {
        public boolean isValid(String s) {
            int length;
        
            do {
                length = s.length();
                s = s.replace("()", "").replace("{}", "").replace("[]", "");
            } while(length != s.length());
        
            return s.length() == 0;
        }
    }
    

    In this solution you essentially can remove parentheses that you know are valid until the string is empty. If the string is not empty, that means that the parentheses were malformed.


  • 14
    E

    The code is easy to understand and the idea is good. However, it might not be considered an efficient algorithm, compared with the stack method. Consider the worst case where the string is as follows:

    [([([([([()])])])])]

    where only one pair of parenthesis can be detected and removed each round, would the running time be O(n^2)?


  • 6
    T

    Nooooo! Stop upvoting it....

    In an algorithms coding community who appreciates constructing 3*n/2 separate String objects to validate a single String? Not to mention that each replace call uses regex:

    • compiles a Pattern
    • creates a Matcher
    • builds the replacement using a StringBuffer ("synchronized StringBuilder")

    Don't get me wrong, regex is awesome, I love it, and use it very often for parsing complex structures. The difference is that for some tasks there are faster ways. Just because a code has less characters it doesn't mean it's better. My outburst is highly correlated to using a regex without knowing it or knowingly in a loop that isn't pre-compiled. Consider the following code:

    public class Solution {
    	private static final Pattern PARENS = Pattern.compile("\\(\\)|\\[\\]|\\{\\}");
    	public boolean isValid(String s) {
    		int length;
    		do {
    			length = s.length();
    			s = PARENS.matcher(s).replaceAll("");
    		} while (length != s.length());
    		return s.isEmpty();
    	}
    }
    

    same result, 1 regex = 1 compile overall, 1 extra string created per iteration; still using StringBuffer though. I would be happier with this, but there's still a way to do it by iterating over the characters of the input once.


  • 0
    E

    Could you explain a little bit more on this? Are you saying that regex is generally not very efficient in Java? How about using split(" ") to parse a string to a string matrix? Is this considered a good way?


  • 0
    T

    Updated with more detail.

    I think your split example is acceptable, it's used once and it gives a relatively useful structure. Though it's a waste if you consider that you'll need to allocate an another array and parse each little string into a number or object for example, or just simply convert it to a multidimensional array.


  • 0
    H

    the idea is great, but the algorithm could be more efficient


Log in to reply
 

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