Dada una array arr[] que consta de N strings de caracteres en minúsculas y un carácter K tal que cualquier string puede comenzar con el carácter K , la tarea es verificar si existe algún par de strings que comiencen y no comiencen (‘!’ ) con el carácter K . Si se encuentra que es cierto , imprima » Sí «. De lo contrario, escriba “ No ”.
Ejemplos:
Entrada: arr[] = {“a”, “!a”, “b”, “!c”, “d”, “!d”}, K = ‘!’
Salida: Sí
Explicación:
Existen pares válidos de las strings {(“a”, “!a”), (“!d”, “d”)}.Entrada: arr[] = {“rojo”, “rojo”, “rojo”, “!naranja”, “amarillo”, “!azul”, “cian”, “!verde”, “marrón”, “!gris” }, K = ‘!’
Salida: Sí
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es encontrar todos los pares posibles de la array y verificar si el par de strings satisface la condición dada o no.
Complejidad de tiempo: O(N 2 *M), donde M es la longitud máxima de la string en la array dada arr[] .
Espacio Auxiliar: O(1)
Enfoque eficiente: el enfoque anterior también se puede resolver usando el diccionario . Siga los pasos a continuación para resolver el problema:
- Inicialice un diccionario , digamos, visitado para almacenar las strings visitadas anteriormente.
- Iterar sobre la lista arr[] y en cada iteración, si el carácter inicial de la string actual es el carácter K , entonces verifique la string sin el carácter K en visited ; de lo contrario, verifique la string con el carácter K en visited . Si se encuentra la string , devuelva » Sí «.
- En cada iteración, agregue la string S en el mapa visitado .
- Después de completar los pasos anteriores, escriba » No » si no se cumplen las condiciones anteriores.
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 whether a pair of
// strings exists satisfying the conditions
string checkhappy(vector<string> arr, char K, int N)
{
// Stores the visited strings
set<string> visited;
// Iterate over the array arr[]
for (string s : arr) {
// If first character of current
// string is K
if(s[0] == K)
if (visited.find(s.substr(1)) != visited.end())
return "Yes";
// Otherwise
else
if (visited.find((K + s)) != visited.end())
return "Yes";
// Adding to the visited
visited.insert(s);
}
return "No";
}
// Driver Code
int main() {
// Given Input
vector<string> arr = {"a", "! a", "b", "! c", "d", "! d"};
char K = '!';
int N = arr.size();
cout << checkhappy(arr, K, N) << endl;
return 0;
}
// This code is contributed Dharanendra L V.
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Function to check whether a pair of
// Strings exists satisfying the conditions
static String checkhappy(String[] arr, char K, int N)
{
// Stores the visited Strings
HashSet<String> visited = new HashSet<String> ();
// Iterate over the array arr[]
for (String s : arr) {
// If first character of current
// String is K
if(s.charAt(0) == K)
if (visited.contains(s.substring(1)))
return "Yes";
// Otherwise
else
if (visited.contains((K + s)))
return "Yes";
// Adding to the visited
visited.add(s);
}
return "No";
}
// Driver Code
public static void main(String[] args) {
// Given Input
String[] arr = {"a", "! a", "b", "! c", "d", "! d"};
char K = '!';
int N = arr.length;
System.out.print(checkhappy(arr, K, N) +"\n");
}
}
// This code is contributed by shikhasingrajput
Python3
# Python program for the above approach # Function to check whether a pair of # strings exists satisfying the conditions def checkhappy(arr, K, N): # Stores the visited strings visited = set() # Iterate over the array arr[] for s in arr: # If first character of current # string is K if(s[0] == K): if s[1:] in visited: return 'Yes' # Otherwise else: if (K + s) in visited: return 'Yes' # Adding to the visited visited.add(s) return "No" # Driver Code if __name__ == '__main__': # Given Input arr = ['a', '! a', 'b', '! c', 'd', '! d'] K = '!' N = len(arr) print(checkhappy(arr, K, N))
Javascript
<script>
// Javascript program for the above approach
// Function to check whether a pair of
// strings exists satisfying the conditions
function checkhappy(arr, K, N)
{
// Stores the visited strings
let visited = new Set();
// Iterate over the array arr[]
for(let s of arr)
{
// If first character of current
// string is K
if (s[0] == K)
{
if (visited.has(s.slice(1)))
return "Yes";
}
// Otherwise
else
{
if (visited.has(K + s))
return "Yes";
}
// Adding to the visited
visited.add(s);
}
return "No";
}
// Driver Code
// Given Input
let arr = [ "a", "! a", "b", "! c",
"d", "! d" ];
let K = "!";
let N = arr.length;
document.write(checkhappy(arr, K, N));
// This code is contributed by gfgking
</script>
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG{
// Function to check whether a pair of
// Strings exists satisfying the conditions
static String checkhappy(String[] arr, char K, int N)
{
// Stores the visited Strings
HashSet<String> visited = new HashSet<String> ();
// Iterate over the array []arr
foreach (String s in arr) {
// If first character of current
// String is K
if(s[0] == K)
if (visited.Contains(s.Substring(1)))
return "Yes";
// Otherwise
else
if (visited.Contains((K + s)))
return "Yes";
// Adding to the visited
visited.Add(s);
}
return "No";
}
// Driver Code
public static void Main(String[] args) {
// Given Input
String[] arr = {"a", "! a", "b", "! c", "d", "! d"};
char K = '!';
int N = arr.Length;
Console.Write(checkhappy(arr, K, N) +"\n");
}
}
// This code contributed by shikhasingrajput
No
Complejidad temporal: O(N)
Espacio auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por vandanakillari54935 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA