My elegant C++ DP solution with detailed explanation


  • 2
    D
    class Solution {
    public:
        int longestValidParentheses(string s) {
            int n = s.size(), longest = 0;
            vector<int> dp(n + 1);
            // there is valid parentheses when there are 
            // at least 2 character
            for (int i = 2; i <= n; i++) {
                // 1 1 3  2  3
                // ( ) ( ( ) )
                //     ^     ^ 
                //     |     |
                //    prev   i
                int prev = i - dp[i - 1] - 1; 
                // if current char is ')' and 
                // the first one before the last streak of valid parentheses is '('
                // we add: 
                // 1. last streak before the new pair
                // 2. the streak inside the new pair
                // 3. the new pair
                if (s[i - 1] == ')' && s[prev - 1] == '(') {
                    dp[i] = dp[prev - 1] + dp[i - 1] + 2;
                    longest = max(longest, dp[i]);
                }
            }
            return longest;
        }
    };
    

  • 0

    Thanks for your sharing. It's nice and beautiful.


Log in to reply
 

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