8ms JAVA solution without Stack(Beats 89.42%)


  • 0

    Using Stack to solve this problem, the code is elegant, but not fast. I got only 10ms with the top Java solution with a stack.

    So, in this solution, only int array and ArrayList are used. The int array is to record the parentheses paired or not. And ArrayList is to record its order.

    Easy to understand.

    class Solution {
        public boolean isValid(String s) {
    		List<Integer> order = new ArrayList<>();
    		char[] cs = s.toCharArray();
    		int[] pair = { 0, 0, 0 };
    		
    		for (int i = 0; i < cs.length; i++) {
    			if (cs[i] == '(') {
    				order.add(0);
    				pair[0]++;
    			} else if (cs[i] == '[') {
    				order.add(1);
    				pair[1]++;
    			} else if (cs[i] == '{') {
    				order.add(2);
    				pair[2]++;
    			} else if (cs[i] == '}') {
    				if (pair[2] > 0 && order.get(order.size() - 1) == 2) {
    					pair[2]--;
    					order.remove(order.size() - 1);
    				} else return false;
    			} else if (cs[i] == ']') {
    				if (pair[1] > 0 && order.get(order.size() - 1) == 1) {
    					pair[1]--;
    					order.remove(order.size() - 1);
    				} else return false;
    			} else if (cs[i] == ')') {
    				if (pair[0] > 0 && order.get(order.size() - 1) == 0) {
    					pair[0]--;
    					order.remove(order.size() - 1);
    				} else return false;
    			} else return false;
    		}
    		
    		if (order.isEmpty()) return true;
    		else return false;
    	}
    }
    

Log in to reply
 

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