Pure 1D-DP without using stack (python) with detailed explanation


  • 15
    P
    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            # use 1D DP
            # dp[i] records the longestValidParenthese EXACTLY ENDING at s[i]
            dp = [0 for x in xrange(len(s))]
            max_to_now = 0
            for i in xrange(1,len(s)):
                if s[i] == ')':
                    # case 1: ()()
                    if s[i-1] == '(':
                        # add nearest parentheses pairs + 2
                        dp[i] = dp[i-2] + 2
                    # case 2: (()) 
                    # i-dp[i-1]-1 is the index of last "(" not paired until this ")"
                    elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                        if dp[i-1] > 0: # content within current matching pair is valid 
                        # add nearest parentheses pairs + 2 + parentheses before last "("
                            dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
                        else:
                        # otherwise is 0
                            dp[i] = 0
                    max_to_now = max(max_to_now, dp[i])
            return max_to_now

  • 2
    R

    Thanks pennllio for the solution. Here is C++ version (8ms) of your solution:

    class Solution {
    public:
        int longestValidParentheses(const string& s) {
            vector<int> v;
            for (int i = 0; i < s.length(); i++) {
                v.push_back(0);
            }
            int mx = 0;
            for (int i = 1; i < s.length(); i++) {
                if(s[i] == ')') {
                    if(s[i-1] == '(') {
                        int val = 0;
                        if(i - 2 >= 0) {
                            val = v[i-2];
                        }
                        v[i] = val + 2;
                        if(mx < v[i]) {
                            mx = v[i];
                        }
                    } else {
                        int j = i - v[i-1] - 1;
                        if (j >= 0) {
                            if(s[j] == '(') {
                                int val = v[i - 1] + 2;
                                if(j - 1 >= 0) {
                                    val = v[i - 1] + 2 + v[j - 1];
                                }
                                v[i] = val;
                                if(mx < v[i]) {
                                    mx = v[i];
                                }
                            }
                        }
                    }
                }
            }
            return mx;
        }
    };

  • 0
    Q
    This post is deleted!

  • 2
    F

    @pennlio

    I think you don't need to add if dp[i-1] >0 ...else...
    I edit your code like this, and the system accepted, did I miss anything?

    class Solution(object):
        def longestValidParentheses(self, s):
            """
            :type s: str
            :rtype: int
            """
            # use 1D DP
            # dp[i] records the longestValidParenthese EXACTLY ENDING at s[i]
            dp = [0 for x in xrange(len(s))]
            max_to_now = 0
            for i in xrange(1,len(s)):
                if s[i] == ')':
                    # case 1: ()()
                    if s[i-1] == '(':
                        # add nearest parentheses pairs + 2
                        dp[i] = dp[i-2] + 2
                    # case 2: (()) 
                    # i-dp[i-1]-1 is the index of last "(" not paired until this ")"
                    elif i-dp[i-1]-1 >= 0 and s[i-dp[i-1]-1] == '(':
                        dp[i] = dp[i-1] + 2 + dp[i-dp[i-1]-2]
                    max_to_now = max(max_to_now, dp[i])
            return max_to_now
    
    

  • 0
    I

    @flyerx right, somehow that's hidden in dp = [0 for x in xrange(len(s))]


  • 3

    @flyerx
    Why do you need another variable max_to_now? You could simply return max(dp)

    Secondly, the condition check if s[i-1] == '(': is unnecessary.

    def longestValidParentheses(self, s):
        s = ')' + s
        dp = [0] * len(s)
        for i in range(1, len(s)):
            if s[i] == ')' and s[i - dp[i - 1] - 1] == '(':
                dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]
        return max(dp)

  • 0
    L

    @lee215 said in Pure 1D-DP without using stack (python) with detailed explanation:

    dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]]

    Could you explain your dp[i] = dp[i - 1] + 2 + dp[i - 2 - dp[i - 1]] function? Not sure how you came up with the last part


  • 0
    B

    thank you for your explantion


  • 0
    Z
                    if s[i - 1] == '(':
                        dp[i] = (0 if i < 2 else dp[i - 2]) + 2
    
    

    I think you should add a check of index out of range


  • 0

    @zpng
    for i in xrange(1,len(s)) So don't need bother a check.
    Secondly, as I said in my previous reply, even the if s[i-1] == '(' is unecessary.


  • 0
    M

    You are not using Stack and using an array.
    In python, we can use array/list as a stack.
    And this stack will consume less memory than the array being used by DP solutions.


  • 0

    python O(n) with stack, beat 93.66%

    class Solution(object):
        def longestValidParentheses(self, s):
            if not s or len(s) < 2: return 0
            stack = []
            leftmost = -1
            res = 0
            for i in range(len(s)):
                if s[i] == '(':
                    stack.append(i)
                else: # case ')'
                    if not stack: # not valid parenthesis, update leftmost
                        leftmost = i
                    else:
                        stack.pop()
                        if not stack: # stack is empty, length is i - leftmost
                            res = max(res, i - leftmost) 
                        else: # otherwise, length is i - last index of stack
                            res = max(res, i - stack[-1]) 
            return res
    

Log in to reply
 

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