Как вывести валидные скобки?

Question

Найти валидные круглые скобки. Обязательно счетчик и правильные скобки нужно выводить.

Пример 1:

Ввод: (()

Вывод: 2 - ()

Пример 2:

Ввод: )()())

Вывод: 4 - ()()

Пример 3:

Ввод: )(()())

Вывод: 6 - (()())

Пример 4:

Ввод: )(

Вывод: 0

Я решил так:

public class ValidParentheses {


  public static void main(String[] args) {
    String parentheses1 = "(()";
    String parentheses2 = ")()())";
    String parentheses3 = ")(()())";
    String parentheses4 = ")(";
    System.out.println(longestValidParentheses(parentheses1) + " - " + getValidParentheses(parentheses1));
    System.out.println(longestValidParentheses(parentheses2) + " - " + getValidParentheses(parentheses2));
    System.out.println(longestValidParentheses(parentheses3) + " - " + getValidParentheses(parentheses3));
    System.out.println(longestValidParentheses(parentheses4) + " - " + getValidParentheses(parentheses4));


  }
  private static String getValidParentheses(String input) {
    int open = 0;
    int ind = 0;

    StringBuilder result = new StringBuilder();

    while (ind < input.length()) {
      char c = input.charAt(ind);
      if (c == '(') {
        open++;
        result.append(c);
      }
      if (c == ')' && open > 0) {
        open--;
        result.append(c);
      }
      ind++;
    }
    while (open > 0) {
      result.append(')');
      open--;
    }
    return result.toString();
  }
  public static int longestValidParentheses(String s) {
    int maxans = 0;
    Stack<Integer> stack = new Stack<>();
    stack.push(-1);
    for (int i = 0; i < s.length(); i++) {
      if (s.charAt(i) == '(') {
        stack.push(i);
      } else {
        stack.pop();
        if (stack.empty()) {
          stack.push(i);
        } else {
          maxans = Math.max(maxans, i - stack.peek());
        }
      }
    }
    return maxans;
  }
}

вывод получается вот такой вот:

2 - (())
4 - ()()
6 - (()())
0 - ()

т.е пример 2 и 3,отработали норм, а 1 и 4,неверно,в чем ошибка?

Answer 1

Чтобы понять, является ли конкретная скобочка валидной, нужно понять, сколько у нас незакрытых скобок слева (если текущая скобка закрывающая) или сколько закрывающих справа (если текущая - открывающая)

Простой код на C#

string longestValidParentheses(string input)
{
    var ret = new StringBuilder();
    var closed = 0;
    for (int i = 0; i < input.Length; i++) if (input[i] == ')') closed++;

    var currentOpen = 0;

    for (int i = 0; i < input.Length; i++)
    {
        if (input[i] == '(' && currentOpen < closed)
        {
            ret.Append(input[i]);
            currentOpen++;
        }
        if (input[i] == ')')
        {
            if (currentOpen > 0)
            {
                ret.Append(input[i]);
                currentOpen--;
            }
            closed--;
        }
    }

    return ret.ToString();
}

Проверка

String parentheses1 = "(()";
String parentheses2 = ")()())";
String parentheses3 = ")(()())";
String parentheses4 = ")(";

Console.WriteLine(longestValidParentheses(parentheses1));
Console.WriteLine(longestValidParentheses(parentheses2));
Console.WriteLine(longestValidParentheses(parentheses3));
Console.WriteLine(longestValidParentheses(parentheses4));

Вывод

()
()()
(()())

UPD Возможно это не является ответом, так как я не понял, можем ли мы менять исходную строку или просто ищем в ней валидную подстроку.

Answer 2

Можно решать в лоб (есть более быстрые варианты) и возвращать сразу строку. Пример на C#

string longestValidParentheses(string input)
{   
    int start = 0;
    int len = 0;
    for(int i=0; i<input.Length; i++){
        for(int j=i+1; j<input.Length; j++){
            if (isValid(input, i, j)){
                var newLen = j-i+1;
                if (newLen > len){
                    len = newLen;
                    start = i;
                }
            }
        }
    }
    
    return input.Substring(start, len);
}

Проверка на валидность

bool isValid(string str, int start, int end){
    
    int open = 0;
    for(int i=start; i<=end; i++)
    {
        if (str[i] == '(') open++;
        if (str[i] == ')'){
            if (open == 0) return false;
            open--;
        }       
    }
    return open == 0;   
}

Проверяем код

String parentheses1 = "(()";
String parentheses2 = ")()())";
String parentheses3 = ")(()())";
String parentheses4 = ")(";

string ret1 = longestValidParentheses(parentheses1);
Console.WriteLine(ret1 + " - " + ret1.Length);

string ret2 = longestValidParentheses(parentheses2);
Console.WriteLine(ret2 + " - " + ret2.Length);

string ret3 = longestValidParentheses(parentheses3);
Console.WriteLine(ret3 + " - " + ret3.Length);

string ret4 = longestValidParentheses(parentheses4);
Console.WriteLine(ret4 + " - " + ret4.Length);

Вывод

() - 2
()() - 4
(()()) - 6
 - 0

БЛОГ НА HUSL

Как вывести валидные скобки?

Ответы (2 шт):