C++ DP solution with detailed thought process and comments


  • 0

    To explain the thought process, let us define a valid closure of parentheses to be
    (...), where ... is either empty or another valid closure.
    The i-th entry in the DP table, longestEndAt[i], represents the length of the longest matching parentheses ending at index i.
    It is easy to see that:

    • If s[i] == '(', longestEndAt[i] should be 0, since no valid parentheses end with '(';

    • If s[i] == ')', then s[i] can potentially be an ending parenthesis of a valid closure, or a dangling parenthesis. We need to look at the previous char (if it exists) to find out

      • If s[i-1] == '(', then s[i] is the ending parenthesis of closure (). This closure gives us length 2, but maybe the there were valid parentheses before this closure, and if there is a such a closure, its length is longestEndAt[i-2]. So longestEndAt[i] = 2 + longestEndAt[i-2].
      • If s[i-1] == ')', then s[i] can potentially be an ending parenthesis of closure (...) where ... is not empty, or it can be a dangling parenthesis. Suppose s[i-1] is not a dangling parenthesis, we know the start of the valid parentheses end at s[i-1] is a '(' at index i-1-longestEndAt[i-1], because longestEndAt[i-1] denote the length of that sequence (a sequence of valid closures). Let's say start = i-1-longestEndAt[i-1] Then, if s[start-1] is a '(', we know s[i] would not be a dangling parenthesis, but an ending parenthesis of a sequence of valid closures starting at start - 1. If not, then s[i] is a dangling parenthesis, we can leave longestEndAt[i] at 0. So longestEndAt[i] = 2 + longestEndAt[i-1] + longestEndAt[start-1]
    int longestValidParentheses(string s) {
        vector<int> longestEndAt(s.size(), 0);
        int longestLen = 0;
        for (int i = 1; i < s.size(); i++) {
        	if (s[i] == ')') {
                // To luce's credit we need to perform out of bound error checking (or hacking)
        	    #define longestAt(i) longestEndAt[i < 0 ? 0 : i]
        	    // easy case, just make sure to check if there is a char before s[i-1]
        	    if (s[i-1] == '(')
        	        longestAt(i) = 2 + longestAt(i-2);
        	    // there is a matching '(' at the beginning of the sequence of closures
        	    else if (s[i-1-longestAt(i-1)] == '(')
        		longestAt(i) = longestAt(i-1) + 2 + longestAt(i-2-longestAt(i-1));
        	    // if not, this is a dangling parenthesis, skip it
        	    // update max
        	    longestLen = max(longestLen, longestAt(i));
        	}
        }
        return longestLen;
    }
    

  • 1
    L

    Was looking at your code trying to figure out how you handled out of bounds errors, for example, "())" test case. Threw me for a loop.

    Found out you don't. Your current code accesses an element outside of the vector and compares it to '('. This is an error in your code.Try using vector.at() or a bounds checker in your code. You can actually access s[-1] and on very slim cases get a return of true.
    Your welcome!


  • 0

    @luce You are right. I didn't check the out of bounds error in my original code and it passed the oj because of luck. I have updated the code to fix the bug. Thanks for pointing out and making me look up vector.at()! Pretty handy stuff.


  • 0
    L

    You still got out of bounds error with longestEndAt[i-2-longestEndAt[i-1]]


  • 0

    @luce Oops. You are right. However I really don't want to add another check to avoid a single case this time, especially because doing so introduces a new line (or break line limit) and would make things look unnecessarily complicated. So I came up with this #define longestAt(i) longestEndAt[i < 0 ? 0 : i] that allows us to skip out of bound error checking altogether since when the index is negative, we always want 0, which longestEndAt[0] happens to be.


  • 0
    L

    Using define is generally bad practice since you are at your compiler's mercy. FYI


  • 0

    @luce I wouldn't do this in production nor in an interview :). It simply doesn't work for most other problems either. But the OP is mainly about an easy-to-understand abstraction so it's nice to have one line that encapsulates the ugliness, I hope.


Log in to reply
 

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