Dada una array arr[] que consta de N strings , la tarea es encontrar el par de strings que no está presente en la array formada por ningún par (arr[i], arr[j]) intercambiando los primeros caracteres de las strings arr[i] y arr[j] .
Ejemplos:
Entrada: arr[] = {“bueno”, “malo”, “comida”}
Salida: 2
Explicación:
Los posibles pares que se pueden formar intercambiando los primeros caracteres de cualquier par son:
- («bueno», «malo»): al intercambiar los caracteres ‘g’ y ‘b’, se modifican las strings a «bood» y gad, que no está presente en la array.
- («malo», «comida»): al intercambiar los caracteres ‘g’ y ‘b’, se modifican las strings a «bood» y gad, que no está presente en la array.
Por lo tanto, la cuenta total es 2.
Entrada: arr[] = {“geek”, “peek”}
Salida: 0
Enfoque ingenuo: el enfoque más simple para resolver el problema dado es generar todos los pares de strings y, para cada par , intercambiar los primeros caracteres de ambas strings y, si ambas strings están presentes en la array, contar este par. Después de verificar todos los pares, imprima el valor del conteo obtenido.
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 count new pairs of strings
// that can be obtained by swapping first
// characters of any pair of strings
void countStringPairs(string a[], int n)
{
// Stores the count of pairs
int ans = 0;
// Generate all possible pairs of
// strings from the array arr[]
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Stores the current
// pair of strings
string p = a[i], q = a[j];
// Swap the first characters
if (p[0] != q[0]) {
swap(p[0], q[0]);
int flag1 = 0;
int flag2 = 0;
// Check if they are already
// present in the array or not
for (int k = 0; k < n; k++) {
if (a[k] == p) {
flag1 = 1;
}
if (a[k] == q) {
flag2 = 1;
}
}
// If both the strings
// are not present
if (flag1 == 0 && flag2 == 0) {
// Increment the ans
// by 1
ans = ans + 1;
}
}
}
}
// Print the resultant count
cout << ans;
}
// Driver Code
int main()
{
string arr[] = { "good", "bad", "food" };
int N = sizeof(arr) / sizeof(arr[0]);
countStringPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
class GFG{
// Function to count new pairs of strings
// that can be obtained by swapping first
// characters of any pair of strings
static void countStringPairs(String a[], int n)
{
// Stores the count of pairs
int ans = 0;
// Generate all possible pairs of
// strings from the array arr[]
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Stores the current
// pair of strings
char p[] = a[i].toCharArray();
char q[] = a[j].toCharArray();
// Swap the first characters
if (p[0] != q[0])
{
char temp = p[0];
p[0] = q[0];
q[0] = temp;
int flag1 = 0;
int flag2 = 0;
// Check if they are already
// present in the array or not
for(int k = 0; k < n; k++)
{
if (a[k].equals(new String(p)))
{
flag1 = 1;
}
if (a[k].equals(new String(q)))
{
flag2 = 1;
}
}
// If both the strings
// are not present
if (flag1 == 0 && flag2 == 0)
{
// Increment the ans
// by 1
ans = ans + 1;
}
}
}
}
// Print the resultant count
System.out.println(ans);
}
// Driver Code
public static void main(String[] args)
{
String arr[] = { "good", "bad", "food" };
int N = arr.length;
countStringPairs(arr, N);
}
}
// This code is contributed by Kingash
Python3
# python 3 program for the above approach # Function to count new pairs of strings # that can be obtained by swapping first # characters of any pair of strings def countStringPairs(a, n): # Stores the count of pairs ans = 0 # Generate all possible pairs of # strings from the array arr[] for i in range(n): for j in range(i + 1, n, 1): # Stores the current # pair of strings p = a[i] q = a[j] # Swap the first characters if (p[0] != q[0]): p = list(p) q = list(q) temp = p[0] p[0] = q[0] q[0] = temp p = ''.join(p) q = ''.join(q) flag1 = 0 flag2 = 0 # Check if they are already # present in the array or not for k in range(n): if (a[k] == p): flag1 = 1 if (a[k] == q): flag2 = 1 # If both the strings # are not present if (flag1 == 0 and flag2 == 0): # Increment the ans # by 1 ans = ans + 1 # Print the resultant count print(ans) # Driver Code if __name__ == '__main__': arr = ["good", "bad", "food"] N = len(arr) countStringPairs(arr, N) # This code is contributed by SURENDRA_GANGWAR.
C#
// C # program for the above approach
using System;
class GFG {
// Function to count new pairs of strings
// that can be obtained by swapping first
// characters of any pair of strings
static void countStringPairs(string[] a, int n)
{
// Stores the count of pairs
int ans = 0;
// Generate all possible pairs of
// strings from the array arr[]
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Stores the current
// pair of strings
char[] p = a[i].ToCharArray();
char[] q = a[j].ToCharArray();
// Swap the first characters
if (p[0] != q[0]) {
char temp = p[0];
p[0] = q[0];
q[0] = temp;
int flag1 = 0;
int flag2 = 0;
// Check if they are already
// present in the array or not
for (int k = 0; k < n; k++) {
if (a[k].Equals(new string(p))) {
flag1 = 1;
}
if (a[k].Equals(new string(q))) {
flag2 = 1;
}
}
// If both the strings
// are not present
if (flag1 == 0 && flag2 == 0) {
// Increment the ans
// by 1
ans = ans + 1;
}
}
}
}
// Print the resultant count
Console.WriteLine(ans);
}
// Driver Code
public static void Main(string[] args)
{
string[] arr = { "good", "bad", "food" };
int N = arr.Length;
countStringPairs(arr, N);
}
}
// This code is contributed by ukasp.
Javascript
<script>
// JavaScript program for the above approach
// Function to count new pairs of strings
// that can be obtained by swapping first
// characters of any pair of strings
function countStringPairs(a, n) {
// Stores the count of pairs
var ans = 0;
// Generate all possible pairs of
// strings from the array arr[]
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
// Stores the current
// pair of strings
var p = a[i];
var q = a[j];
// Swap the first characters
if (p[0] !== q[0]) {
p = p.split("");
q = q.split("");
var temp = p[0];
p[0] = q[0];
q[0] = temp;
p = p.join("");
q = q.join("");
var flag1 = 0;
var flag2 = 0;
// Check if they are already
// present in the array or not
for (let k = 0; k < n; k++) {
if (a[k] === p) flag1 = 1;
if (a[k] === q) flag2 = 1;
}
// If both the strings
// are not present
if (flag1 === 0 && flag2 === 0) {
// Increment the ans
// by 1
ans = ans + 1;
}
}
}
}
// Print the resultant count
document.write(ans);
}
// Driver Code
var arr = ["good", "bad", "food"];
var N = arr.length;
countStringPairs(arr, N);
</script>
Producción:
2
Complejidad de tiempo: O(N 3 )
Espacio auxiliar: O(M), donde M es el tamaño más grande de la string presente en la array, A[]
Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso del concepto Hashing . Siga los pasos a continuación para resolver el problema:
- Inicialice una variable, digamos ans como 0 para almacenar el posible recuento de pares de strings.
- Inicialice un HashMap , diga M para almacenar todas las strings presentes en la array arr[] .
- Atraviese la array , arr[] e incremente la aparición de arr[i ] en M.
- Iterar en el rango [0, N – 1] usando la variable i y realizar los siguientes pasos:
- Iterar en el rango [i + 1, N – 1] usando la variable j y realizar los siguientes pasos:
- Almacene el par actual de strings en dos strings temporales, digamos p y q .
- Intercambia el primer carácter de las strings p y q .
- Si las strings p y q no están presentes en HashMap , M , entonces incremente el valor de ans en 1 .
- Iterar en el rango [i + 1, N – 1] usando la variable j y realizar los siguientes pasos:
- Después de completar los pasos anteriores, imprima el valor de ans como resultado.
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 count newly created pairs
// by swapping the first characters of
// any pairs of strings
void countStringPairs(string a[], int n)
{
// Stores the count all possible
// pair of strings
int ans = 0;
// Push all the strings
// into the Unordered Map
unordered_map<string, int> s;
for (int i = 0; i < n; i++) {
s[a[i]]++;
}
// Generate all possible pairs of
// strings from the array arr[]
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
// Store the current
// pair of strings
string p = a[i];
string q = a[j];
// Swap the first character
if (p[0] != q[0]) {
swap(p[0], q[0]);
// Check if both string
// are not present in map
if (s.find(p) == s.end()
&& s.find(q) == s.end()) {
ans++;
}
}
}
}
// Print the result
cout << ans;
}
// Driver Code
int main()
{
string arr[] = { "good", "bad", "food" };
int N = sizeof(arr) / sizeof(arr[0]);
countStringPairs(arr, N);
return 0;
}
Java
// Java program for the above approach
import java.lang.*;
import java.util.*;
class GFG{
// Function to count newly created pairs
// by swapping the first characters of
// any pairs of strings
static void countStringPairs(String a[], int n)
{
// Stores the count all possible
// pair of strings
int ans = 0;
// Push all the strings
// into the Unordered Map
Map<String, Integer> s = new HashMap<>();
for(int i = 0; i < n; i++)
{
s.put(a[i], s.getOrDefault(a[i], 0));
}
// Generate all possible pairs of
// strings from the array arr[]
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Store the current
// pair of strings
StringBuilder p = new StringBuilder(a[i]);
StringBuilder q = new StringBuilder(a[j]);
// Swap the first character
if (p.charAt(0) != q.charAt(0))
{
char t = p.charAt(0);
p.setCharAt(0, q.charAt(0));
q.setCharAt(0, t);
// Check if both string
// are not present in map
if (!s.containsKey(p.toString()) &&
!s.containsKey(q.toString()))
{
ans++;
}
}
}
}
// Print the result
System.out.println(ans);
}
// Driver code
public static void main(String[] args)
{
String arr[] = {"good", "bad", "food"};
int N = arr.length;
countStringPairs(arr, N);
}
}
// This code is contributed by offbeat
Python3
# Python3 program for the above approach
# Function to count newly created pairs
# by swapping the first characters of
# any pairs of strings
def countStringPairs(a, n):
# Stores the count all possible
# pair of strings
ans = 0
# Push all the strings
# into the Unordered Map
s = {}
for i in range(n):
s[a[i]] = s.get(a[i], 0) + 1
# Generate all possible pairs of
# strings from the array arr[]
for i in range(n):
for j in range(i + 1, n):
# Store the current
# pair of strings
p = [i for i in a[i]]
q = [j for j in a[j]]
# Swap the first character
if (p[0] != q[0]):
p[0], q[0] = q[0], p[0]
# Check if both string
# are not present in map
if (("".join(p) not in s) and
("".join(q) not in s)):
ans += 1
# Print the result
print (ans)
# Driver Code
if __name__ == '__main__':
arr = [ "good", "bad", "food" ]
N = len(arr)
countStringPairs(arr, N)
# This code is contributed by mohit kumar 29
Javascript
<script>
// Javascript program for the above approach
// Function to count newly created pairs
// by swapping the first characters of
// any pairs of strings
function countStringPairs(a, n)
{
// Stores the count all possible
// pair of strings
let ans = 0;
// Push all the strings
// into the Unordered Map
let s = new Map();
for(let i = 0; i < n; i++)
{
if(!s.has(a[i]))
s.set(a[i],0);
s.set(a[i], s.get(a[i]) + 1);
}
// Generate all possible pairs of
// strings from the array arr[]
for(let i = 0; i < n; i++)
{
for(let j = i + 1; j < n; j++)
{
// Store the current
// pair of strings
let p = (a[i]).split("");
let q = (a[j]).split("");
// Swap the first character
if (p[0] != q[0])
{
let t = p[0];
p[0] = q[0];
q[0] = t;
// Check if both string
// are not present in map
if (!s.has(p.join("")) &&
!s.has(q.join("")))
{
ans++;
}
}
}
}
// Print the result
document.write(ans);
}
// Driver code
let arr=["good", "bad", "food"];
let N = arr.length;
countStringPairs(arr, N);
// This code is contributed by avanitrachhadiya2155
</script>
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
// Function to count newly created pairs
// by swapping the first characters of
// any pairs of strings
static void countStringPairs(string[] a, int n)
{
// Stores the count all possible
// pair of strings
int ans = 0;
// Push all the strings
// into the Unordered Map
Dictionary<string,int> s = new Dictionary<string,int>();
for(int i = 0; i < n; i++)
{
if(!s.ContainsKey(a[i]))
s.Add(a[i],0);
s[a[i]]++;
}
// Generate all possible pairs of
// strings from the array arr[]
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++)
{
// Store the current
// pair of strings
char[] p = (a[i]).ToCharArray();
char[] q = (a[j]).ToCharArray();
// Swap the first character
if (p[0] != q[0])
{
char t = p[0];
p[0]=q[0];
q[0]=t;
// Check if both string
// are not present in map
if (!s.ContainsKey(new string(p)) &&
!s.ContainsKey(new string(q)))
{
ans++;
}
}
}
}
// Print the result
Console.WriteLine(ans);
}
// Driver code
static public void Main ()
{
string[] arr = {"good", "bad", "food"};
int N = arr.Length;
countStringPairs(arr, N);
}
}
// This code is contributed by rag2127.
Producción:
2
Tiempo Complejidad: O(N 2 )
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por lokeshpotta20 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA