LeetCode has a Hard coding Problem in Its’ Algorithm Section “Longest Valid Parentheses”. Today We are going to solve this problem. LeetCode Link of the Problem is HERE
Given a string containing just the characters
')', find the length of the longest valid (well-formed) parentheses substring.
Input: s = "(()" Output: 2 Explanation: The longest valid parentheses substring is "()".
Input: s = ")()())" Output: 4 Explanation: The longest valid parentheses substring is "()()".
Input: s = "" Output: 0
0 <= s.length <= 3 * 104
Solution to Longest Valid Parentheses
Skeleton Code given in Leetcode is
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """
1. Method violence taken every substring O (N ^ 2), then use the method in question 20 determines whether it is legally O (N), the total time of O (N ^ 3).
2. Violence Solution traversed for one string O (N), from each character, the total number of the left bracket and a right bracket number, and length of each record satisfies the O (N) when the number of left and right bracket == Numbers in parentheses, if left Number of parentheses <number of right parentheses, continue. The time complexity is O(N^2).
3. Stack local stack process with the longest substring matching simulation, after again traversing, namely matching the rest of the stack is not on the brackets, between which the string position, i.e. to meet the requirements, which take a longest. O(N).
class Solution(object): def longestValidParentheses(self, s): """ :type s: str :rtype: int """ stack= for i in xrange(len(s)): if s[i]=='(' or not stack: stack.append(i) else: t=stack.pop() if s[t] == ')': stack.append(t) stack.append(i) right,longest=len(s),0 while stack: left=stack.pop() longest=max(longest,right-left-1) right=left return max(longest,right)
Python-related posts Visit HERE
C++ related posts Visit HERE
Databases related posts Visit HERE
Data Structures related posts visit HERE
Algorithms related posts visit HERE
Data Science related posts visit HERE