Java solution using NO stack


  • 0
    T

    idea is kind of like a compiler (actually LL compiler), the recursive() method consumes a valid set of paren

    public class Solution {
        int cursor = 0;
        public boolean isValid(String s) {
            char ss[] = s.toCharArray();
            while(cursor<s.length()){
              if (recursive(ss)==false) return false;  
            } 
            return true;
        }
        
    
    	boolean recursive(char[] ss) {
    		char open = ss[cursor++];
    		if (open != '(' && open != '[' && open != '{')
    			return false;
    		while (cursor < ss.length) {
    
    			char next = ss[cursor];
    
    			if (next == '(' || next == '[' || next == '{') {
    				if (recursive(ss) == false)
    					return false;
    			} else
    				break;
    		}
    		
    		if (cursor == ss.length)
    			return false;
    
    		return match(open, ss[cursor++]);
    	}
    	
        
        boolean match(char a, char b) {
            return a=='(' && b == ')' || a=='[' && b == ']' || a == '{' && b == '}';
        }
    }

  • 0
    T

    Nice, you're using the JVM/CPU's call stack as a stack :)


Log in to reply
 

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