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

31.12.2019Массивы, Строки

Для заданной строки скобок задача состоит в том, чтобы найти индекс 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

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

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
?>

Выход:

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

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

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

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

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

0.00 (0%) 0 votes