Regex Solution


  • 0
    B

    The idea comes from a very similar solution hinted by Stefan Pochmann in Verifying Preorder Traversal. We keep on replacing occurrences of the strings "{}", "[]" and "()" in the parent string and updating it each time. If at any time we do not find occurrence of any of the above three in the string, we quit out and see if the string turned out to be empty. Since the characters '{', '}', '[', ']', '(' & ')' carry special meaning in Regular expressions, replace them with other 'simple' characters (say '(' -> 'a', ')' -> 'b' etc.)

    public boolean isValid(String s) {
            s = s.replace('{','a');
            s = s.replace('}','b');
            s = s.replace('(','c');
            s = s.replace(')','d');
            s = s.replace('[','e');
            s = s.replace(']','f');
            while(s.indexOf("ab") >= 0 || s.indexOf("cd") >= 0 || s.indexOf("ef") >= 0){
                s = s.replaceAll("ab","");
                s = s.replaceAll("cd","");
                s = s.replaceAll("ef","");
            }
            return s.isEmpty();
    }
    

Log in to reply
 

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