Длинная Действительны Скобках


Это "длинная действительны скобки" проблему leetcode.com:

Дана строка, содержащая только символы "(" и ")", найти длину самого длинного допустимого (хорошо сформированной) скобки подстроки. Для "(()"самый длинный действующий скобки подстроки "()", который имеет длину 2. Другой пример ")()())", где самый длинный действующий скобки подстроки "()()", который имеет длину 4.

Я изучал этот вопрос во время интервью макет интервью. И я был в состоянии проверить его против тестов.

Начните с самой длинной длины, и использовать стек, чтобы определить, если это является допустимым. Если нет, length - 1.

Индекс элементы в строку в стек, если " ( " , то добавить в стек. Если бы ")" если стек не пуст, если s[stack.top()] == "(", stack.pop()иначе stack.push(i). Если стек пуст, stack.push(i).

Наиболее важная идея заключается в том, что подстрока между соседними индексами в стек действует.Наиболее важным моментом динамического программирования является то, что подстрочный j представляют. Пусть дольше быть массив ДП. longest[i] самая длинная подстрока заканчивается у меня.

def longestValidParentheses(self, s):
        """
        :type s: str
        :rtype: 
        """
        if len(s) <= 1: return 0
        longest = [0] * len(s)
        max_len = 0
        for i in range(1, len(s)):
            if s[i] == ")":
                if s[i-1] == "(":
                    longest[i] = 2 + (longest[i-2] if i - 2>= 0 else 0)
                    print "hrere"
                    print longest[i]
                    if longest[i] > max_len: max_len = longest[i]
                else:
                    if i - longest[i-1] - 1 >= 0 and s[i-longest[i-1]-1] == "(":
                        longest[i] = 2 + longest[i-1] + (longest[i-longest[i-1]-2] if i-longest[i-1]-2 >= 0 else 0)
                        if longest[i] > max_len: max_len = longest[i]
        return max_len


Комментарии
1 ответ

1. Комментарий


  1. Есть пара print заявления, что, кажется, осталось от отладки сессии. Если вы хотите отследить выполнение программы на Python, вы можете сделать это без правки кода, с помощью Python отладчика. Это позволит избежать риск забыть снять код отладки.

  2. Нет необходимости в особом случае:

    if len(s) <= 1: return 0

    поскольку эти случаи обрабатываются корректно остальной код.


  3. Также нет необходимости в специальном случае:

    if s[i-1] == "(":

    поскольку если вы посмотрите на две ветки, вы увидите, что они делают то же самое.


  4. Алгоритм немного сложно, поэтому я хотел бы иметь комментарий, объясняющий значения, которые мы собираемся положить в массив longest:

    # longest[i] will be length of longest valid substring ending at i.

  5. Выражение i - longest[i-1] - 1 появляется в нескольких местах, так что было бы очень полезно сохранить в переменной:

    # Index where matching ( would have to be, if it exists.
    j = i - longest[i-1] - 1

  6. Тест i-longest[i-1]-2 >= 0 становится j-1 >= 0 и это может быть упрощен до j > 0 чтобы избежать вычитания, а потом просто j поскольку вы уже опробовали j >= 0.

  7. Мы можем избежать испытаний j на всех, отметив, что если это 0 тогда j-1 это -1 и longest[-1] по-прежнему действителен поиска, получения последней записи массива longest, который 0 как требовалось.

  8. Линии:

    if longest[i] > max_len: max_len = longest[i]

    может быть упрощена с помощью встроенного max:

    max_len = max(max_len, longest[i])

  9. Вместо того, чтобы поддерживать рабочее максимальное, просто запустите max один раз в конце:

    return max(longest, default=0)

    Это требуется Python 3.4 или более поздней версии, для default аргумент. На более ранних версиях Python вы бы писать что-то вроде:

    return max(longest) if longest else 0

2. Пересмотренный кодекс

# longest[i] will be length of longest valid substring ending at i.
longest = [0] * len(s)
for i in range(1, len(s)):
if s[i] == ')':
# Index where matching ( would have to be, if it exists.
j = i - longest[i-1] - 1
if j >= 0 and s[j] == '(':
longest[i] = 1 + i - j + longest[j-1]
return max(longest, default=0)

5
ответ дан 30 января 2018 в 12:01 Источник Поделиться