Рубрики

Найти равную точку в строке скобок

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

Точка равенства — это такой индекс, что число открывающих скобок перед ним равно числу закрывающих скобок от и после.

Примеры:

Input : str = "(())))("
Output:   4
After index 4, string splits into (())
and ))(. Number of opening brackets in the 
first part is equal to number of closing 
brackets in the second part.

Input : str = "))"
Output: 2
As after 2nd position i.e. )) and "empty"
string will be split into these two parts:
So, in this number of opening brackets i.e.
0 in the first part is equal to number of 
closing brackets in the second part i.e. 
also 0.

Спросил в: Amazon

  1. Хранить количество открывающих скобок в строке до каждого индекса, оно должно начинаться с начального индекса.
  2. Аналогично, в строке до каждого индекса появляется «Сохранить количество закрывающих скобок», но это следует делать из последнего индекса.
  3. Проверьте, имеет ли какой-либо индекс одинаковое значение открывающей и закрывающей скобок.

C ++

// C ++ программа для поиска индекса k, который
// решает количество открывающих скобок
// равно количеству закрывающих скобок
#include<bits/stdc++.h>

using namespace std;

  
// Функция для поиска равного индекса

int findIndex(string str)

{

    int len = str.length();

    int open[len+1], close[len+1];

    int index = -1;

    memset(open, 0, sizeof (open));

    memset(close, 0, sizeof (close));

  

    open[0] = 0;

    close[len] = 0;

    if (str[0]=='(')

        open[1] = 1;

    if (str[len-1] == ')')

        close[len-1] = 1;

  

    // Сохраняем количество открывающих скобок

    // на каждый индекс

    for (int i = 1; i < len; i++)

    {

        if ( str[i] == '(' )

            open[i+1] = open[i] + 1;

        else

            open[i+1] = open[i];

    }

  

    // Сохраняем количество закрывающих скобок

    // на каждый индекс

    for (int i = len-2; i >= 0; i--)

    {

        if ( str[i] == ')' )

            close[i] = close[i+1] + 1;

        else

            close[i] = close[i+1];

    }

  

    // проверяем, нет ли открытия или закрытия

    // скобки

    if (open[len] == 0)

        return len;

    if (close[0] == 0)

        return 0;

  

    // проверяем, есть ли индекс

    // обе скобки равны

    for (int i=0; i<=len; i++)

        if (open[i] == close[i])

            index = i;

  

    return index;

}

  
// Код драйвера

int main()

{

    string str = "(()))(()()())))";

    cout << findIndex(str);

    return 0;

}

Джава

// Java-программа для поиска индекса k, который
// решает количество открывающих скобок
// равно количеству закрывающих скобок

  

public class GFG 

{

    // Метод поиска равного индекса

    static int findIndex(String str)

    {

        int len = str.length();

        int open[] = new int[len+1];

        int    close[] = new int[len+1];

        int index = -1;

       

        open[0] = 0;

        close[len] = 0;

        if (str.charAt(0)=='(')

            open[1] = 1;

        if (str.charAt(len-1) == ')')

            close[len-1] = 1;

       

        // Сохраняем количество открывающих скобок

        // на каждый индекс

        for (int i = 1; i < len; i++)

        {

            if ( str.charAt(i) == '(' )

                open[i+1] = open[i] + 1;

            else

                open[i+1] = open[i];

        }

       

        // Сохраняем количество закрывающих скобок

        // на каждый индекс

        for (int i = len-2; i >= 0; i--)

        {

            if ( str.charAt(i) == ')' )

                close[i] = close[i+1] + 1;

            else

                close[i] = close[i+1];

        }

       

        // проверяем, нет ли открытия или закрытия

        // скобки

        if (open[len] == 0)

            return len;

        if (close[0] == 0)

            return 0;

      

        // проверяем, есть ли индекс

        // обе скобки равны

        for (int i=0; i<=len; i++)

            if (open[i] == close[i])

                index = i;

       

        return index;

    }

      

    // Метод драйвера

    public static void main(String[] args)

    {

        String str = "(()))(()()())))";

        System.out.println(findIndex(str));

    }

}

Python 3

# Способ найти равный индекс

def findIndex(str):

    l = len(str)

    open = [None] * (l + 1)

    close = [None] * (l + 1)

    index = -1

      

    open[0] = 0

    close[l] = 0

    if (str[0]=='('):

        open[1] = 1

    if (str[l - 1] == ')'):

        close[l - 1] = 1

      

    # Храните количество

    # открывающие скобки

    # в каждом индексе

    for i in range(1, l):

        if (str[i] == '('):

            open[i + 1] = open[i] + 1

        else:

            open[i + 1] = open[i]

      

    # Храните номер

    # закрывающих скобок

    # в каждом индексе

    for i in range(l - 2, -1, -1):

        if ( str[i] == ')'):

            close[i] = close[i + 1] + 1

        else:

            close[i] = close[i + 1]

      

    # проверить, нет ли

    # открывающие или закрывающие скобки

    if (open[l] == 0):

        return len

    if (close[0] == 0):

        return 0

      

    # проверить, есть ли

    # индекс, при котором оба

    # скобки равны

    for i in range(l + 1):

        if (open[i] == close[i]):

            index = i

      

    return index

      
Код водителя

str = "(()))(()()())))"

print(findIndex(str))

  
# Этот код добавлен
# by ChitraNayal

C #

// C # программа для поиска индекса
// k, который решает число
// открывающих скобок равно
// к числу закрывающих скобок

using System;

  

class GFG 

{
// Метод поиска равного индекса

static int findIndex(string str)

{

    int len = str.Length;

    int[] open = new int[len + 1];

    int[] close = new int[len + 1];

    int index = -1;

  

    open[0] = 0;

    close[len] = 0;

    if (str[0] == '(')

        open[1] = 1;

    if (str[len - 1] == ')')

        close[len - 1] = 1;

  

    // Сохраняем количество

    // открывающие скобки

    // на каждый индекс

    for (int i = 1; i < len; i++)

    {

        if (str[i] == '(')

            open[i + 1] = open[i] + 1;

        else

            open[i + 1] = open[i];

    }

  

    // Сохраняем номер

    // закрывающих скобок

    // на каждый индекс

    for (int i = len - 2; i >= 0; i--)

    {

        if (str[i] == ')')

            close[i] = close[i + 1] + 1;

        else

            close[i] = close[i + 1];

    }

  

    // проверить нет ли

    // открытие или закрытие

    // скобки

    if (open[len] == 0)

        return len;

    if (close[0] == 0)

        return 0;

  

    // проверяем, есть ли

    // индекс, при котором оба

    // скобки равны

    for (int i = 0; i <= len; i++)

        if (open[i] == close[i])

            index = i;

  

    return index;

}

  
// Код драйвера

public static void Main()

{

    string str = "(()))(()()())))";

    Console.Write(findIndex(str));

}
}

  
// Этот код добавлен
// ChitraNayal

PHP

<?php
// Метод поиска равного индекса

function findIndex($str)

{

    $len = strlen($str);

    $open = array(0, $len + 1, NULL);

    $close = array(0, $len + 1, NULL);

    $index = -1;

      

    $open[0] = 0;

    $close[$len] = 0;

    if ($str[0] == '(')

    $open[1] = 1;

    if ($str[$len - 1] == ')')

    $close[$len - 1] = 1;

      

    // Сохраняем номер

    // открывающих скобок

    // на каждый индекс

    for ($i = 1; $i < $len; $i++)

    {

        if ($str[$i] == '(')

            $open[$i + 1] = $open[$i] + 1;

        else

            $open[$i + 1] = $open[$i];

    }

      

    // Сохраняем номер

    // закрывающих скобок

    // на каждый индекс

    for ($i = $len - 2; $i >= 0; $i--)

    {

        if ($str[$i] == ')')

        $close[$i] = $close[$i + 1] + 1;

        else

        $close[$i] = $close[$i + 1];

    }

      

    // проверить нет ли

    // открытие или закрытие

    // скобки

    if ($open[$len] == 0)

        return $len;

    if ($close[0] == 0)

        return 0;

      

    // проверяем, есть ли

    // индекс, при котором оба

    // скобки равны

    for ($i = 0; $i <= $len; $i++)

        if ($open[$i] == $close[$i])

            $index = $i;

      

    return $index;

}

      
// Код драйвера

$str = "(()))(()()())))";

echo (findIndex($str));

  
// Этот код добавлен
// ChitraNayal
?>


Выход:

9

Сложность времени: O (n)

Эта статья предоставлена Сахилом Чхаброй (Акку) . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти равную точку в строке скобок

0.00 (0%) 0 votes