Simple DP Solution in Python

  • 0

    This solution is originally done by another person. It took me sometime to understand the code. I added some comments to make it easier to understand so people can save time, hopefully.
    Here is the link

    class Solution:
        # @param {string} s
        # @return {integer}
        # Dynamic Programming
        def longestValidParentheses(self, s):
            max_len = 0
            #Use dictionary not list to reduce time
            start_pos = {} # DP1 variable
            stack = []
            for i in range(len(s)):
                if s[i] == '(':
                    #Only the valid ')' has a chance to change max_len
                    if stack:
                        last = stack.pop()
                        start_pos[i] = last # DP2 State
                        #If the ')' right before '(' matching current valid '(' is also valid
                        if start_pos.has_key(last-1):
                            #Set start position of current ')' to the start position of the former ')'
                            start_pos[i] = start_pos[last - 1] # DP2 State
                        max_len = max(max_len, i - start_pos[i] + 1) #DP3 Transit
            return max_len

Log in to reply

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