Ac solution code


  • 0

    The basic idea is using stack to do pair matching, as the following:

    Update - Nov 24, 2015:

    Added the optimized version, can easily add or remove paired patterns, e.g. (), {}, []

    Optimized Version:

    public boolean isValid(String s) {
    	if (s == null || s.isEmpty())
    		return false;
    	Map<Character, Character> pairs = new HashMap<Character, Character>();
    	pairs.put('{', '}');
    	pairs.put('(', ')');
    	pairs.put('[', ']');
    	
    	Stack<Character> stack = new Stack<Character>();
    	for (Character cur : s.toCharArray()) {	    		
    		if (pairs.containsKey(cur)) {
    			stack.push(cur);
    		} else {
    			if (stack.isEmpty())
    				return false;
    			char ch = (char)stack.pop();
    			if (pairs.get(ch) != cur) {
    	    		return false;
    	    	}
    		}	    	
    	}    	
    	return stack.isEmpty();
    }
    

    Old Version:

    public boolean isValid(String s) {
    	if (s==null || s.length()==0) return false;
    	Stack<Character>stack = new Stack<Character>();
    	
    	for (char ch : s.toCharArray()) {
    		if ("{[(".contains(String.valueOf(ch)))
    			stack.push(ch);
    		else {
    			if (stack.isEmpty()) 
    				return false;
    			char cur = stack.pop();
    			if(cur=='{' && ch != '}'
    			|| cur=='(' && ch != ')'
    			|| cur=='[' && ch != ']')
    				return false;					
    		}
    	}
    	return stack.isEmpty();
    }

Log in to reply
 

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