Dada una string S y una lista de strings subs[] que almacena las substrings de S y todas las substrings están presentes solo una vez, la tarea es encerrar las substrings de S que existen en subs[] entre paréntesis. Si las substrings en subs[] se superponen entre sí o son consecutivas, combínelas en un conjunto de paréntesis.
Ejemplos:
Entrada : S = “abcdefgh”, subs = {“ef”, “bc”, “g”}
Salida : “a(bc)d(efg)h”
Explicación : las substrings “ef” y “g” son consecutivas.
Por lo tanto, están encerrados dentro de un conjunto de paréntesis.
La substring «bc» está encerrada dentro de un conjunto de paréntesisEntrada: S = “abcdefgh”, subs = [“abcde”, “bc”]
Salida: “(abcde)fgh”
Explicación: Las substrings “abcde” y “bc” se superponen.
Por lo tanto, están encerrados dentro de un conjunto de paréntesis.
Planteamiento: La idea para resolver el problema es la siguiente:
Podemos encontrar el índice inicial y final de cada substring de subs[] en la string S . Entonces pueden considerarse como intervalos separados y podemos usar el concepto de fusionar intervalos superpuestos para fusionarlos y encerrarlos entre paréntesis.
Siga los siguientes pasos para implementar la idea:
- Cree una lista para almacenar las posiciones de apertura y cierre de cada substring de subs[].
- Combine estos intervalos de posiciones de apertura y cierre. Para eso haz lo siguiente:
- Ordene todos los intervalos por posición de apertura en orden ascendente.
- Comenzando con el primer intervalo, recorra los intervalos ordenados y haga lo siguiente para cada intervalo:
- Si el intervalo actual no es el intervalo inicial y se superpone con el intervalo anterior, combínelos.
- De lo contrario, agregue el intervalo actual a la lista de intervalos de salida.
- Revise la lista de intervalos combinados e inserte los paréntesis correspondientes en la string S .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ code to implement the approach
#include <bits/stdc++.h>
using namespace std;
// Function that takes a set of
// intervals, merges overlapping and
// contigous intervals and
// returns the merged intervals
vector<vector<int> >
mergeIntervals(vector<vector<int> >& interval)
{
// Stores the new indices after
// merging
vector<vector<int> > mergedInterval;
int start = interval[0][0];
int end = interval[0][1];
for (int i = 1; i < interval.size(); i++) {
// Intervals merge so update end index
if (interval[i][0] <= end
|| interval[i][0] == end + 1) {
end = max(end, interval[i][1]);
}
else {
// Intervals don't merge so
// add current interval to
// mergedInterval
vector<int> al;
al.push_back(start);
al.push_back(end);
mergedInterval.push_back(al);
// Update start and end index
start = interval[i][0];
end = interval[i][1];
}
}
// Add last interval to merged interval
vector<int> al;
al.push_back(start);
al.push_back(end);
mergedInterval.push_back(al);
return mergedInterval;
}
// Function finds the starting and
// ending position of
// substring in given input string
vector<int> findSubStringIndex(string subStr, string s)
{
int i = 0, j = subStr.length();
while (j <= s.length()) {
if (s.substr(i, j - i) == subStr) {
return { i, j - 1 };
}
j++;
i++;
}
return {};
}
// Function to add parentheses at given index
string addParentheses(string s, string subs[])
{
// Interval stores the opening,
// closing position of each
// substring in subs
vector<vector<int> > interval(subs->size(),
vector<int>(2));
// Loop through each substring in
// subs and add the opening and
// closing positions into intervals
for (int i = 0; i < subs->size(); i++) {
interval[i] = findSubStringIndex(subs[i], s);
}
// Sort the intervals according to
// opening index position
sort(begin(interval), end(interval));
vector<vector<int> > mergedInterval
= mergeIntervals(interval);
string sb;
int pre = 0;
// Add the opening and closing
// brackets at the positions from
// mergedIntervals
for (auto& arr : mergedInterval) {
sb += s.substr(pre, arr[0] - pre);
sb += '(';
sb += s.substr(arr[0], arr[1] + 1 - arr[0]);
sb += ')';
pre = arr[1] + 1;
}
sb += s.substr(pre, s.size() - pre);
return sb;
}
// Driver Code
int main()
{
string S = "abcdefgh";
string subs[] = { "ef", "bc", "g" };
// Function call
cout << addParentheses(S, subs) << "\n";
return 0;
}
// This code is contributed by Rohit Pradhan
Java
// Java code to implement the approach
import java.io.*;
import java.util.*;
class GFG {
// Function to add parentheses at given index
static String addParentheses(String s,
String[] subs)
{
// Interval stores the opening,
// closing position of each
// substring in subs
int[][] interval = new int[subs.length][2];
// Loop through each substring in
// subs and add the opening and
// closing positions into intervals
for (int i = 0; i < subs.length; i++) {
interval[i] = findSubStringIndex(subs[i], s);
}
// Sort the intervals according to
// opening index position
Arrays.sort(interval, (a, b) -> a[0] - b[0]);
ArrayList<ArrayList<Integer> > mergedInterval
= mergeIntervals(interval);
StringBuilder sb = new StringBuilder();
int pre = 0;
// Add the opening and closing
// brackets at the positions from
// mergedIntervals
for (ArrayList<Integer> arr : mergedInterval) {
sb.append(s.substring(pre, arr.get(0)));
sb.append("(");
sb.append(
s.substring(arr.get(0),
arr.get(1) + 1));
sb.append(")");
pre = arr.get(1) + 1;
}
sb.append(s.substring(pre, s.length()));
String ans = new String(sb);
return ans;
}
// Function that takes a set of
// intervals, merges overlapping and
// contigous intervals and
// returns the merged intervals
private static ArrayList<ArrayList<Integer> >
mergeIntervals(int[][] interval)
{
// Stores the new indices after
// merging
ArrayList<ArrayList<Integer> > mergedInterval
= new ArrayList<>();
int start = interval[0][0];
int end = interval[0][1];
for (int i = 1; i < interval.length; i++) {
// Intervals merge so update end index
if (interval[i][0] <= end
|| interval[i][0] == end + 1) {
end = Math.max(end,
interval[i][1]);
}
else {
// Intervals don't merge so
// add current interval to
// mergedInterval
ArrayList<Integer> al
= new ArrayList<>();
al.add(start);
al.add(end);
mergedInterval.add(al);
// Update start and end index
start = interval[i][0];
end = interval[i][1];
}
}
// Add last interval to merged interval
ArrayList<Integer> al
= new ArrayList<>();
al.add(start);
al.add(end);
mergedInterval.add(al);
return mergedInterval;
}
// Function finds the starting and
// ending position of
// substring in given input string
static int[] findSubStringIndex(String subStr,
String s)
{
int i = 0, j = subStr.length();
while (j <= s.length()) {
if (s.substring(i, j).equals(subStr)) {
return new int[] { i, j - 1 };
}
j++;
i++;
}
return null;
}
// Driver Code
public static void main(String[] args)
{
String S = "abcdefgh";
String[] subs = { "ef", "bc", "g" };
// Function call
System.out.println(addParentheses(S, subs));
}
}
Python3
# Python 3 code to implement the approach
# Function that takes a set of
# intervals, merges overlapping and
# contigous intervals and
# returns the merged intervals
def mergeIntervals(interval):
# Stores the new indices after merging
mergedInterval = []
start = interval[0][0]
end = interval[0][1]
for i in range(1, len(interval)):
# Intervals merge so update end index
if interval[i][0] <= end or interval[i][0] == end+1:
end = max(end, interval[i][1])
else:
# Intervals don't merge so
# add current interval to
# mergedInterval
al = []
al.append(start)
al.append(end)
mergedInterval.append(al)
# Update start and end index
start = interval[i][0]
end = interval[i][1]
# Add last interval to merged interval
al = []
al.append(start)
al.append(end)
mergedInterval.append(al)
return mergedInterval
# Function finds the starting and
# ending position of
# substring in given input string
def findSubStringIndex(subStr, s):
i = 0
j = len(subStr)
while(j < len(s)):
if s[i:j] == subStr:
return [i, j-1]
j += 1
i += 1
# Function to add parentheses at given index
def addParentheses(s, subs):
# Interval stores the opening,
# closing position of each
# substring in subs
interval = [0]*len(subs)
# Loop through each substring in
# subs and add the opening and
# closing positions into intervals
for i in range(len(subs)):
interval[i] = findSubStringIndex(subs[i], s)
# Sort the intervals according to
# opening index position
interval.sort()
mergedInterval = mergeIntervals(interval)
sb = ""
pre = 0
# Add the opening and closing
# brackets at the positions from
# mergedIntervals
for arr in mergedInterval:
sb += s[pre:arr[0]]
sb += '('
sb += s[arr[0]:arr[1] + 1]
sb += ')'
pre = arr[1] + 1
sb += s[pre:len(s)]
return sb
# Driver code
S = "abcdefgh"
subs = ['ef', 'bc', 'g']
print(addParentheses(S, subs))
'''This code is contributed by RAJAT KUMAR...'''
Javascript
<script>
// JavaScript code to implement the approach
// Function that takes a set of
// intervals, merges overlapping and
// contigous intervals and
// returns the merged intervals
function mergeIntervals(interval)
{
// Stores the new indices after
// merging
let mergedInterval = [];
let start = interval[0][0];
let end = interval[0][1];
for (let i = 1; i < interval.length; i++) {
// Intervals merge so update end index
if (interval[i][0] <= end
|| interval[i][0] == end + 1) {
end = Math.max(end, interval[i][1]);
}
else {
// Intervals don't merge so
// add current interval to
// mergedInterval
let al = [];
al.push(start);
al.push(end);
mergedInterval.push(al);
// Update start and end index
start = interval[i][0];
end = interval[i][1];
}
}
// Add last interval to merged interval
let al = [];
al.push(start);
al.push(end);
mergedInterval.push(al);
return mergedInterval;
}
// Function finds the starting and
// ending position of
// substring in given input string
function findSubStringIndex(subStr, s)
{
let i = 0, j = subStr.length;
while (j <= s.length) {
if (s.substring(i, j) == subStr) {
return [ i, j - 1 ];
}
j++;
i++;
}
return [];
}
// Function to add parentheses at given index
function addParentheses(s,subs)
{
// Interval stores the opening,
// closing position of each
// substring in subs
let interval = new Array(subs.length).fill(0).map(()=>new Array(2));
// Loop through each substring in
// subs and add the opening and
// closing positions into intervals
for (let i = 0; i < subs.length; i++) {
interval[i] = findSubStringIndex(subs[i], s);
}
// Sort the intervals according to
// opening index position
interval.sort((a,b)=>a[0]-b[0]);
let mergedInterval = mergeIntervals(interval);
let sb = "";
let pre = 0;
// Add the opening and closing
// brackets at the positions from
// mergedIntervals
for (let arr of mergedInterval) {
sb += s.substring(pre, arr[0]);
sb += '(';
sb += s.substring(arr[0], arr[1] + 1);
sb += ')';
pre = arr[1] + 1;
}
sb += s.substring(pre, s.length);
return sb;
}
// Driver Code
let S = "abcdefgh";
let subs = [ "ef", "bc", "g" ];
// Function call
document.write(addParentheses(S, subs),"</br>");
// This code is contributed by shinjanpatra
</script>
Producción
a(bc)d(efg)h
Complejidad de tiempo: O(N*logN + N*M) donde N es el tamaño de subs[] y M es la longitud de S
Espacio auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por amrithabpatil y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA