Non-stack java solution


  • 0
    E

    i implemented a divide and conquer solution without a stack, was wondering if anyone knows how it compares with solutions that use a stack (runtime, space, etc)

    public class Solution {
        public boolean isValid(String s) {
            // return false if null
            if (s == null) return false;
    
            // return true if empty
            if (s.equals("")) return true;
    
            // %2 == 1 is a guaranteed mismatch
            if (s.length() % 2 == 1) return false;
            
            // first bracket
            String first = s.substring(0, 1);
            
            // non-open means mismatch
            if ("([{".indexOf(first) == -1) return false;
            
            // find the index of it's match
            int index = matchIndexOf(first, s);
            
            // not found means mismatch
            if (index == -1) return false;
            
            // if match not at end of s
            if (index != s.length())
            {
                // divide and conquer
                return isValid(strip(s.substring(0, index))) && isValid(s.substring(index));
            }
            // otherwise, strip the brackets and try again
            else
            {
                return isValid(strip(s));
            }
        }
        
        // find matching paren
        public int matchIndexOf(String first, String s)
        {
            String match;
            // get the matching bracket
            // s is guarenteed to be an open bracket
            switch(first)
            {
                case "(":
                    match = ")";
                    break;
                case "[":
                    match = "]";
                    break;
                default:
                    match = "}";
            }
            
            // how "deep" we are
            int level = 1;
    
            // index we're checking
            int index = 1;
            
            // while we haven't found the match
            while (level != 0)
            {
                // if we've hit the end of the string, we didn't find a match
                if (index == s.length()) return -1;
    
                // if we find another first, we go to next depth
                if (s.substring(index, index + 1).equals(first)) level += 1;
    
                // if we find a match, we come up a depth
                else if (s.substring(index, index + 1).equals(match)) level -= 1;
    
                // increment index
                index += 1;
            }
            
            // if we make it this far, we've found our match
            // return its index
            return index;
        }
        
        // strip off end brackets
        public String strip(String str)
        {
            return str.substring(0, str.length() - 1).substring(1);
        }
    }

Log in to reply
 

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