подстроки со сбалансированными круглыми скобками

Question

В моем интервью был задан следующий вопрос: для строки, состоящей только из '(' и ')'. найти общее количество подстрок со сбалансированными скобками. Примечание: входная строка уже сбалансирована.

Единственное решение, которое я могу придумать, это грубая сила, которая занимает n^3 раза. Есть ли более быстрое решение. Если есть, то я также хотел бы знать, как это сделать.

Answer 1

Предположим, что конечный результат будет в целочисленном R. Вы должны сканировать слева направо на струне Затем, вы должны держать стек Z, и обновлять его по мере сканирования слева направо.

Вы должны сначала нажать 0 на Z. Когда вы столкнетесь с '(' при индексе i, вы должны нажать 0 на S. Когда вы столкнетесь с ')' в индексе i, вы должны увеличивать R на (T * (T + 1)/2), T - верхний элемент Z. Затем вы должны поместить T и прирастить новый верхний элемент на 1.

После завершения сканирования вы должны увеличить R на один больше времени на (T * (T + 1)/2), так как все еще есть элемент T в Z, который мы изначально поставили.

Сканирование с использованием стека Z должно принимать линейное время. Ниже представлена ​​не очень эффективная реализация Python, которую, надеюсь, легко понять.

def solve(s): 
    R = 0 
    Z = [0] 
    for i in range(0, len(s)): 
     if s[i] == '(': 
      Z.append(0) 
     else: 
      R += Z[-1] * (Z[-1] + 1)/2 
      Z = Z[:-1] 
      Z[-1] += 1 
    R += Z[-1] * (Z[-1] + 1)/2 
    return R 

Идея создания приращения R заключается в следующем. В основном вы сохраняете номер последовательных сбалансированных строк на одном уровне, пока они не выйдут из этого уровня. Затем, когда вы собираетесь перейти на более высокий уровень (т. Е. Когда знает, не будет никакой другой одноуровневой и последовательной подстроки, мы обновим решение.

Значение T * (T + 1)/2 можно понять, если вы немного поразмыслите об интервалах. Давайте перечислим эти последовательные сбалансированные подстроки на одном уровне от 1 до T. Теперь выбор сбалансированных подстрок, используя их, в основном составляет начальную и конечную точку для нашего большего Подстрока. Если в качестве отправной точки выбрать подстроку # 1, то в качестве конечной точки мы можем выбрать другие подстроки. Для # 2 существуют (T-1) и т. д. В основном существуют T * (T + 1)/2 разных интервала, которые мы можем выбрать в качестве допустимой подстроки с балансировкой, поэтому мы увеличиваем R на это значение.

Последняя операция приращения, применяемая к R, - это просто не опускать внешний уровень.

Answer 2

Я сделал простой алгоритм, который бы разрешил вашу проблему. Обратите внимание, что он не ищет вложенных сбалансированных круглых скобок.

function TestAlgorithm(testString, resultCounter) 
{ 
    if (!resultCounter) 
     resultCounter = 0; 

    var startIndex = testString.indexOf('('); 

    if (startIndex === -1) 
     return resultCounter; 

    var endIndex = testString.indexOf(')', startIndex) 

    if (endIndex === -1) 
     return resultCounter; 

    var newTestString = testString.substring(endIndex); 

    return TestAlgorithm(newTestString, ++resultCounter); 
} 

Answer 3

Каждая подстрока это в рамках начинается с «(» Так что мой нерекурсивна подход будет:.

total = 0 
while string is not empty { 
    count valid substrings beginning here -- add to total 
    trim leading '(' and trailing ')' from string 
    trim leading ')' and trailing '(' from string if present 
} 

count valid substrings beginning here может быть сделано с помощью пошагового полукокса по полукокса, инкремент счетчика, когда вы видите " ('и декремент, когда вы видите') '. Когда декремент приводит к нулю, вы находитесь на закрытии') 'сбалансированной подстроки.