Найдите длину самой длинной действующей последовательности в строке, в O (n) времени

Question

Мой друг столкнулся с вопросом в интервью, и ему сказали, что есть решение O (n). Однако ни один из нас не может придумать это. Возникает вопрос:

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

Например ")()())", самые длинные действительные скобки является ()(), а длина равен 4.

я понял это с динамическим программированием, но это не означает О (п). Есть идеи?

public int getLongestLen(String s) { 
    if (s == null || s.length() == 0) 
     return 0; 

    int len = s.length(), maxLen = 0; 
    boolean[][] isValid = new boolean[len][len]; 
    for (int l = 2; l < len; l *= 2) 
     for (int start = 0; start <= len - l; start++) { 
      if ((s.charAt(start) == '(' && s.charAt(start + l - 1) == ')') && 
       (l == 2 || isValid[start+1][start+l-2])) { 
        isValid[start][start+l-1] = true; 
        maxLen = Math.max(maxLen, l); 
       } 
     } 

    return maxLen; 
} 

Answer 1

Я делал этот вопрос раньше, и нелегко придумать решение O (n) под давлением. Вот он, который решается с помощью стека.

private int getLongestLenByStack(String s) { 
    //use last to store the last matched index 
    int len = s.length(), maxLen = 0, last = -1; 
    if (len == 0 || len == 1) 
     return 0; 

    //use this stack to store the index of '(' 
    Stack<Integer> stack = new Stack<Integer>(); 
    for (int i = 0; i < len; i++) { 
     if (s.charAt(i) == '(') 
      stack.push(i); 
     else { 
      //if stack is empty, it means that we already found a complete valid combo 
      //update the last index. 
      if (stack.isEmpty()) { 
       last = i;   
      } else { 
       stack.pop(); 
       //found a complete valid combo and calculate max length 
       if (stack.isEmpty()) 
        maxLen = Math.max(maxLen, i - last); 
       else 
       //calculate current max length 
        maxLen = Math.max(maxLen, i - stack.peek()); 
      } 
     } 
    } 

    return maxLen; 
} 

Answer 2

Вы можете увеличивать/уменьшать переменную int для каждой открытой скобки/закрывающей скобки соответственно. Следите за количеством таких действительных операций (где переменная не опускается ниже 0) в качестве текущей длины и отслеживайте самый длинный - например, макс.

public int getLongestLen(String s) { 
    if (s == null || s.length() == 0) { 
     return 0;  
    } 

    int stack = 0; 
    int counter = 0; 
    int max = 0; 

    for (Character c: s.toCharArray()) { 
     if (c == '(') { 
      stack++; 
     } 
     if (c == ')') { 
      stack--; 
     } 
     if (stack >= 0) { 
      counter++; 
     } 
     if (stack < 0) { 
      counter = 0; 
      stack = 0; 
     } 
     if (counter > max && stack == 0) { 
      max = counter; 
     } 
    } 

    return max; 
} 

Answer 3

просто придумал решение, сделать комментарий, если есть что-нибудь

count = 0 //stores the number of longest valid paranthesis 
empty stack s 
arr[]; //contains the string which has the input, something like())(()(
while(i<sizeof(arr)) 
{ 
    if(a[i] == '(') 
    { 
     if(top == ')') //top of a stack, 
     { 
      count = 0; 
      push a[i] in stack; 
     } 
    } 
    else 
    { 
     if(top == '(') 
     { 
      count+=2; 
      pop from stack; 
     } 
     else 
     { 
      push a[i] in stack; 
     } 
    } 
} 

Количество печати

Answer 4

АЛГОРИТМ: Entire code on GitHub
1. Добавить в стек
1,1 инициализировать - 1, ручка)) без ((
2. Когда вы видите) pop from stack
2.a, если размер стека == 0 (нет совпадений), текущие значения индекса тока
2.b, если размер стека> 0 (совпадение), получить максимальную длину, вычитая индекс значения сверху из текущего индекса (совершенно злой!)

def longestMatchingParenthesis(a): 
    pstack = []  #index position of left parenthesis 
    pstack.append(-1) #default value; handles) without (and when match adds up to 2! 
    stack_size = 1 
    result = 0 
    for i in range(0,len(a)): 
      if a[i] == '(': 
        pstack.append(i) #Append current index 
        stack_size += 1 
      else: # handle) 
        pstack.pop() 
        stack_size -= 1 
        #determine length of longest match! 
        if stack_size > 0: 
          #difference of current index - index at top of the stack (yet to be matched) 
          result = max(result, i - pstack[-1]) 
        else: 
          #stack size == 0, append current index 
          pstack.append(i) 
          stack_size += 1 
    return result 

a = ["()()()", "", "((((", "(((()", "(((())(", "()(()" ,"()(())"] 
for x in a: 
    print("%s = %s" % (x,longestMatchingParenthesis(x))) 

#output 
()()() = 6 
= 0 
((((= 0 
(((() = 2 
(((())(= 4 
()(() = 2 
()(()) = 6 

Answer 5

Просьба найти простейшее рабочее решение.

#include "stdafx.h" 
#include <string> 
#include <vector> 
#include <iostream> 
#include <stack> 
int findMaxLen(string str) 
{ 
int n = str.length(); 

// Create a stack. 
stack<char> stk; 


// Initialize result 
int result = 0; 

// Traverse all characters of given string 
for (int i = 0; i<n; i++) 
{ 
    // If opening bracket, push char '(' of it 
    if (str[i] == '(') 
     stk.push(str[i]); 

    else // If closing bracket, i.e.,str[i] = ')' 
    { 
     if (!stk.empty()) 
     { 
      stk.pop(); 
      result += 2;     
     }   
    } 
} 

return result; 
} 

Answer 6

Нам нужно сохранить индексы ранее начальных скобок в стеке.

Мы нажимаем первый элемент стека в качестве специального элемента как «-1» или любое другое число, которое не встречается в индексах.

Теперь мы пересекаем через строку, когда мы сталкиваемся с «(» фигурными скобками мы помещаем их, иначе, когда мы сталкиваемся с «)» мы первым совать их и

Если стек не пуст, мы находим длину максимума в силе подстроку до этой точки, взяв максимум результата (инициализированный как ноль) и разницу между текущим индексом и индексом в верхней части стека.

Else, если стек пуст, мы нажимаем указатель.

int result=0; 
stack<int> s1; 
s1.push(-1); 
for(int i=0;i<s.size();++i) 
{ 
    if(s[i]=='(') 
     s1.push(i); 

    else if(s[i]==')') 
    { 
     s1.pop(); 

     if(!s1.empty()) 
      result=max(result,i-s1.top()); 
     else 
      s1.push(i); 
    } 
} 
cout<<result<<endl; 

Здесь находится «строка» и «s1» - это стек.

Answer 7

Решение ниже имеет сложность времени O (n) и сложность пространства O (1).

Это очень интуитивно понятно.

Сначала мы пересекаем строку слева направо, ищем самую длинную допустимую подстроку парен, используя метод count, который обычно используется для проверки правильности параметров parens. При этом мы также записываем максимальную длину такой подстроки, если она найдена.

Затем мы делаем то же самое, идя справа налево.


Алгоритм будет выглядеть следующим образом:

// Initialize variables 

1. count = 0, len = 0, max_len_so_far = 0 


// Check for longest valid string of parens while traversing from left to right 

2. iterate over input string from left to right: 
    - len += 1 
    - if next character is '(', 
     count += 1 
    - if next character is ')', 
     count -= 1 
    - if (count == 0 and len > max_len_so_far), 
     max_len_so_far = len 
    - if (count < 0), 
     len = 0, count = 0 


// Set count and len to zero again, but leave max_len_so_far untouched 

3. count = 0, len = 0 


// Now do a very similar thing while traversing from right to left 
// (Though do observe the switched '(' and ')' in the code below) 

4. iterate over input string from right to left: 
    - len += 1 
    - if next character is ')', 
     count += 1 
    - if next character is '(', 
     count -= 1 
    - if (count == 0 and len > max_len_so_far), 
     max_len_so_far = len 
    - if (count < 0), 
     len = 0, count = 0 


// max_len_so_far is now our required answer 

5. Finally, 
    return max_len_so_far 

В качестве примера рассмотрим строковое

"((())" 

Пусть эта строка нулевой индексируются.

Сначала мы идем влево.

Таким образом, при индексе 0 счет будет равен 1, затем 2 по индексу 1, 3 по индексу 2, 2 по индексу 3 и 1 по индексу 4. На этом этапе max_len даже не изменится, поскольку счет снова не 0.

Затем мы идем направо налево.

При индексе 4 счетчик равен 1, затем 2 по индексу 3, затем 1 по индексу 2, затем 0 по индексу 1.
В этот момент len равно 4 и max_len_so_far = 0, поэтому мы устанавливаем max_len = 4.
Затем, при индексе 0, счет равен 1.

На этом этапе мы останавливаем и возвращаем 4, что действительно является правильным ответом.



Доказательство правильности остается в качестве инклюзивного упражнения для читателя.

ПРИМЕЧАНИЕ. Этот алгоритм также может быть очень просто изменен, чтобы вернуть самую длинную допустимую подстроку скобок, а не только ее длину.