Dada una array arr[] que consta de N strings binarias , la tarea es contar el número de strings que no contienen ninguna intersección de arco .
Conectar pares consecutivos de letras idénticas usando Arcos, si se obtiene una intersección, entonces se conoce como Intersección de Arco . A continuación se muestra la ilustración del mismo.
Ejemplos:
Entrada: arr[] = {“0101”, “0011”, “0110”}
Salida: 2
Explicación: La string “0101” tiene intersección de arco. Por lo tanto, el recuento de strings que no tienen ninguna intersección de arco es 2.Entrada: arr[] = {“0011”, “0110”, “00011000”}
Salida: 3
Explicación: todas las strings dadas no tienen ninguna intersección de arco. Por lo tanto, la cuenta es 3.
Enfoque ingenuo: el enfoque más simple es recorrer la array y verificar cada string, si los caracteres similares se agrupan en índices consecutivos o no. Si se encuentra que es cierto, siga incrementando el conteo de tales strings. Finalmente, imprime el valor de conteo obtenido.
Complejidad de tiempo: O(N*M 2 ), donde M es la longitud máxima de string en la array dada.
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es usar Stack . Siga los pasos a continuación para resolver el problema:
- Inicialice count para almacenar el recuento de strings que no contienen ninguna intersección de arco.
- Inicialice una pila para almacenar cada carácter de la string en ella.
- Iterar la string dada y realizar las siguientes operaciones:
- Empuje el carácter actual en la pila .
- Si el tamaño de la pila es mayor que 2 , compruebe si los dos elementos en la parte superior de la pila son iguales o no. Si se determina que es cierto, extraiga ambos caracteres para eliminar la intersección de arco más cercana.
- Después de completar los pasos anteriores, si la pila está vacía , entonces no contiene ninguna intersección de arco.
- Siga el Paso 2 al Paso 4 para cada string en la array para verificar si la string contiene una intersección de arco o no. Si no contiene, cuente esta string.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to check if there is arc
// intersection or not
int arcIntersection(string S, int len)
{
stack<char> stk;
// Traverse the string S
for (int i = 0; i < len; i++) {
// Insert all the elements in
// the stack one by one
stk.push(S[i]);
if (stk.size() >= 2) {
// Extract the top element
char temp = stk.top();
// Pop out the top element
stk.pop();
// Check if the top element
// is same as the popped element
if (stk.top() == temp) {
stk.pop();
}
// Otherwise
else {
stk.push(temp);
}
}
}
// If the stack is empty
if (stk.empty())
return 1;
return 0;
}
// Function to check if there is arc
// intersection or not for the given
// array of strings
void countString(string arr[], int N)
{
// Stores count of string not
// having arc intersection
int count = 0;
// Iterate through array
for (int i = 0; i < N; i++) {
// Length of every string
int len = arr[i].length();
// Function Call
count += arcIntersection(
arr[i], len);
}
// Print the desired count
cout << count << endl;
}
// Driver Code
int main()
{
string arr[] = { "0101", "0011", "0110" };
int N = sizeof(arr) / sizeof(arr[0]);
// Function Call
countString(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG
{
// Function to check if there is arc
// intersection or not
static int arcIntersection(String S, int len)
{
Stack<Character> stk = new Stack<>();
// Traverse the String S
for (int i = 0; i < len; i++)
{
// Insert all the elements in
// the stack one by one
stk.push(S.charAt(i));
if (stk.size() >= 2)
{
// Extract the top element
char temp = stk.peek();
// Pop out the top element
stk.pop();
// Check if the top element
// is same as the popped element
if (stk.peek() == temp)
{
stk.pop();
}
// Otherwise
else
{
stk.add(temp);
}
}
}
// If the stack is empty
if (stk.isEmpty())
return 1;
return 0;
}
// Function to check if there is arc
// intersection or not for the given
// array of Strings
static void countString(String arr[], int N)
{
// Stores count of String not
// having arc intersection
int count = 0;
// Iterate through array
for (int i = 0; i < N; i++)
{
// Length of every String
int len = arr[i].length();
// Function Call
count += arcIntersection(
arr[i], len);
}
// Print the desired count
System.out.print(count +"\n");
}
// Driver Code
public static void main(String[] args)
{
String arr[] = { "0101", "0011", "0110" };
int N = arr.length;
// Function Call
countString(arr, N);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach # Function to check if there is arc # intersection or not def arcIntersection(S, lenn): stk = [] # Traverse the string S for i in range(lenn): # Insert all the elements in # the stack one by one stk.append(S[i]) if (len(stk) >= 2): # Extract the top element temp = stk[-1] # Pop out the top element del stk[-1] # Check if the top element # is same as the popped element if (stk[-1] == temp): del stk[-1] # Otherwise else: stk.append(temp) # If the stack is empty if (len(stk) == 0): return 1 return 0 # Function to check if there is arc # intersection or not for the given # array of strings def countString(arr, N): # Stores count of string not # having arc intersection count = 0 # Iterate through array for i in range(N): # Length of every string lenn = len(arr[i]) # Function Call count += arcIntersection(arr[i], lenn) # Print the desired count print(count) # Driver Code if __name__ == '__main__': arr = [ "0101", "0011", "0110" ] N = len(arr) # Function Call countString(arr, N) # This code is contributed by mohit kumar 29
C#
// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG
{
// Function to check if there is arc
// intersection or not
static int arcIntersection(String S, int len)
{
Stack<char> stk = new Stack<char>();
// Traverse the String S
for (int i = 0; i < len; i++)
{
// Insert all the elements in
// the stack one by one
stk.Push(S[i]);
if (stk.Count >= 2)
{
// Extract the top element
char temp = stk.Peek();
// Pop out the top element
stk.Pop();
// Check if the top element
// is same as the popped element
if (stk.Peek() == temp)
{
stk.Pop();
}
// Otherwise
else
{
stk.Push(temp);
}
}
}
// If the stack is empty
if (stk.Count == 0)
return 1;
return 0;
}
// Function to check if there is arc
// intersection or not for the given
// array of Strings
static void countString(String []arr, int N)
{
// Stores count of String not
// having arc intersection
int count = 0;
// Iterate through array
for (int i = 0; i < N; i++)
{
// Length of every String
int len = arr[i].Length;
// Function Call
count += arcIntersection(
arr[i], len);
}
// Print the desired count
Console.Write(count +"\n");
}
// Driver Code
public static void Main(String[] args)
{
String [] arr = { "0101", "0011", "0110" };
int N = arr.Length;
// Function Call
countString(arr, N);
}
}
// This code is contributed by jana_sayantan.
Javascript
<script>
// JavaScript program for the above approach
// Function to check if there is arc
// intersection or not
function arcIntersection(S, len)
{
var stk = [];
// Traverse the string S
for (var i = 0; i < len; i++) {
// Insert all the elements in
// the stack one by one
stk.push(S[i]);
if (stk.length >= 2) {
// Extract the top element
var temp = stk[stk.length-1];
// Pop out the top element
stk.pop();
// Check if the top element
// is same as the popped element
if (stk[stk.length-1] == temp) {
stk.pop();
}
// Otherwise
else {
stk.push(temp);
}
}
}
// If the stack is empty
if (stk.length==0)
return 1;
return 0;
}
// Function to check if there is arc
// intersection or not for the given
// array of strings
function countString(arr, N)
{
// Stores count of string not
// having arc intersection
var count = 0;
// Iterate through array
for (var i = 0; i < N; i++) {
// Length of every string
var len = arr[i].length;
// Function Call
count += arcIntersection(
arr[i], len);
}
// Print the desired count
document.write( count + "<br>");
}
// Driver Code
var arr = ["0101", "0011", "0110" ];
var N = arr.length;
// Function Call
countString(arr, N);
</script>
Producción:
2
Complejidad de tiempo: O(N*M), donde M es la longitud máxima de string en la array dada.
Espacio auxiliar: O(M), donde M es la longitud máxima de string en la array dada.
Publicación traducida automáticamente
Artículo escrito por chahattekwani71 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA