Участник:Danillich/LongestValidParentheses

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/longest-valid-parentheses/

Достаточно простое решение. Пробегаем строку слева направо, подсчитывая количество открывающих и закрывающих скобок отдельно. Если они равны, то найдена правильная подпоследовательность и считается ее длина. Если количество закрывающих превышает количество открывающих, то значения обнуляются и поиск продолжается (Правильной скобочной последовательности уже не найти, если не обнулить). Аналогично, строка пробегается справа налево, только значения обнуляются, когда количество открывающих скобок превышает количество закрывающих.

 
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        maxlen = 0
 
        opening = 0
        closing = 0
        #forward pass
        for ch in s:
            if ch == '(':
                opening += 1
            else:
                closing += 1
            if opening == closing:
                maxlen = max(2*opening, maxlen)
            elif closing > opening:
                opening = 0
                closing = 0
 
        opening = 0
        closing = 0
        #backward pass
        for ch in reversed(s):
            if ch == '(':
                opening += 1
            else:
                closing += 1
            if opening == closing:
                maxlen = max(2*opening, maxlen)
            elif closing < opening:
                opening = 0
                closing = 0
 
        return maxlen