my solution


  • 0
    F
    1. I think 101210-1-2-1-2
    2. I seprate the parentheses
      1 1 1
      -1 -1 -1
      And I found some rules in that shape.
    3. Think about how the human resolve this problem.
      1 1 1
      -1 -1 -1

    0- 1 0
    0 0 -1
    Then, I can find the rule
    So make it with for-grammar, while+for
    And count the length of sequencial zeros.

    1. while-for is timeout, so I make it with only for-grammar O(n).
      With same rule but use two stacks. One for ( and one for ).
    2. But still time limit So I think more and find there is no use of ) stack.
      So I rearrange my codes and finally get the answer.
    public class Solution {
        public int longestValidParentheses(String s) {
    		Integer[] digitalArray = new Integer[s.length()];
    		char[] charArray = s.toCharArray();
    		Stack left = new Stack();
    
    		int i=0;
    		for (char each : charArray) {
    			if (each == '(') {
    				digitalArray[i] = 1;
    				left.push(i);
    			} else {
    				digitalArray[i] = -1;
    				if (left.size() > 0) {
    					int leftIndex = (int) left.pop();
    
    					digitalArray[leftIndex] = 0;
    					digitalArray[i] = 0;
    				}
    			}
    			i++;
    		}
    
    		int longest = 0;
    		int check = 0;
    		for (int j : digitalArray) {
    			  if ( j == 0) {
    				  check++;
    			  } else {
    				  longest = Math.max(longest, check);
    				  check = 0;
    			  }
    		}
    		longest = Math.max(longest, check);
    		return longest;
        }
    }
    

Log in to reply
 

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