Simple Java solution.


  • 17
    P

    enter image description here

    public int longestValidParentheses(String s) {
        char[] S = s.toCharArray();
        int[] V = new int[S.length];
        int open = 0;
        int max = 0;
        for (int i=0; i<S.length; i++) {
        	if (S[i] == '(') open++;
        	if (S[i] == ')' && open > 0) {
        		V[i] = 2 + V[i-1] + (i-2-V[i-1] > 0 ? V[i-2-V[i-1]] : 0);
        		open--;
        	}
        	if (V[i] > max) max = V[i];
        }
        return max;
    }

  • 2
    S

    Can you explain this part?

    (i-2-V[i-1] > 0 ? V[i-2-V[i-1]] : 0)
    

    My understanding is 2 is itself, V[i-1] is its previous consecutive parentheses, i-2-V[i-1] is the position right outside this big "( ... )" part. So check if previous big "(...)" is a valid one. Is that correct?


  • 0
    P

    Yes. Correct.


  • 0
    S

    Thank you for replying


  • 1
    B

    Thank you for your submission, but I think this part:

    V[i] = 2 + V[i-1] + (i-2-V[i-1] > 0 ? V[i-2-V[i-1]] : 0);
    

    is more readable if you do this:

    V[i] = 2 + V[i-1];
    if(i-V[i] >= 0) {
        V[i] += V[i-V[i]];
    }
    

  • 0
    C

    open is not necessary, because the pair position is already defined by V[i-1-V[i-1]], it can either be '(' or ')', in the first case your open is always >=0, and in second case, it's <0


  • 0
    T

    Mr. balint, why aren't you checking & subtracting -2 as is done by Mr. pavel-shlyk


  • 0
    B

    Dear saumeel_yogesh,

    You can translate one to the other. Let's see:

    V[i] = 2 + V[i-1];
    if(i-V[i] >= 0) {
      V[i] += V[i-V[i]];
    }
    

    From the second line you can replace every V[i] which is on the right side to 2 + V[i-1]. So you get:

    V[i] = 2 + V[i-1];
    if(i-2-V[i-1] >= 0) {
        V[i] += V[i-2-V[i-1]];
    }
    

    And now you can rephrase it like the OP wrote:

    V[i] = 2 + V[i-1] + (i-2-V[i-1] >= 0) ? V[i-2-V[i-1]] : 0;
    

  • 0
    T

    Oh yes!
    Such a stupid question.
    Thank you, Mr. balint


  • 0
    X

    @therealfakebatman lol Mr. balint doesn't know you are trolling xD


  • 0
    W

    It is short.. but not simple.. rather complex logic to comprehend.


Log in to reply
 

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