C++ two different solutions: greedy and DP with comments


  • 1

    Greedy with two pointers:
    Idea is to search from both left to right and right to left to find the max length.

    class Solution {
    private:
        int find(string s, char inc) {       // always search from left to right
            int l = 0, r = 0, cnt = 0, ans = 0;
            
            while (r < s.length()) {
                cnt += s[r++] == inc ? 1 : -1;  // inc is either '(' or ')' as a sign to increase cnt
                if (cnt == 0) {                 // found a valid parentheses substring
                    ans = max(ans, r - l);      // update the max length
                } else if (cnt < 0) {           
                    l = r, cnt = 0;             // if encounter an invalid char, clear cnt and update l
                }
            }
            
            return ans;
        }
    
    public:
        int longestValidParentheses(string s) {
            if (s == "") { return 0; }
            // Search from both left->right and right->left
            return max(find(s, '('), find(string(s.rbegin(), s.rend()), ')'));
        }
    };
    

    DP:

    int longestValidParentheses(string s) {
            vector<int> dp(s.length(), 0);
            int cnt = 0, ans = 0;
            
            for (int i = 0; i < s.length(); i++) {
                if (s[i] == '(') {
                    cnt++;
                } else if (cnt > 0) {
                    cnt--;
                    
                    dp[i] = 2;
                    // for case where s[i - 1] is valid ')'
                    dp[i] += (i - 1) >= 0 ? dp[i - 1] : 0;
                    // for case where it can concatinate previous '(...)'
                    dp[i] += (i - dp[i]) >= 0 ? dp[i - dp[i]] : 0;
    
                    ans = max(ans, dp[i]);
                } 
            }
            
            return ans;
        }
    

Log in to reply
 

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