FAANG 인터뷰 질문| 가장 긴 유효한 괄호
2235 단어 pythonprogrammingstack
예 1:
Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".
예 2:
Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".
예 3:
Input: s = ""
Output: 0
제약:
해결책 1:
# O(n) time | O(n) space - where n is the length of the input string
def longestBalancedSubstring(string):
stack = [-1]
longest = 0
for idx in range(len(string)):
ch = string[idx]
if ch == "(":
stack.append(idx)
else:
stack.pop()
if len(stack) == 0:
stack.append(idx)
else:
top = stack[-1]
longest = max(longest, idx - top)
return longest
더 나은 솔루션
# O(n) time | O(1) space - where n is the length of the input string
def longestBalancedSubstring(string):
return max(
get_longest_sub_string_count(string, True),
get_longest_sub_string_count(string, False)
)
def get_longest_sub_string_count(string, left_to_right):
open_ch= "(" if left_to_right else ")"
step = 1 if left_to_right else -1
idx = 0 if left_to_right else len(string) - 1
open_count = 0
close_count = 0
longest = 0
while idx > -1 and idx < len(string):
ch = string[idx]
if ch == open_ch:
open_count +=1
else:
close_count += 1
if close_count == open_count:
longest = max(longest, open_count*2)
elif close_count > open_count:
open_count = 0
close_count = 0
idx += step
return longest
Reference
이 문제에 관하여(FAANG 인터뷰 질문| 가장 긴 유효한 괄호), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://dev.to/imsazzad/google-interview-question-longest-valid-parentheses-47j0텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)