Ram y Shyam quieren elegir un sitio web para aprender a programar y ambos tienen una lista de sitios web favoritos representados por strings.
Debe ayudarlos a descubrir su interés común con la menor suma de índice. Si hay un empate en la elección entre las respuestas, imprímalas todas sin requisito de orden. Suponga que siempre existe una respuesta.
Ejemplos:
Input : ["GeeksforGeeks", "Udemy", "Coursera", "edX"]
["Codecademy", "Khan Academy", "GeeksforGeeks"]
Output : "GeeksforGeeks"
Explanation : GeeksforGeeks is the only common website
in two lists
Input : ["Udemy", "GeeksforGeeks", "Coursera", "edX"]
["GeeksforGeeks", "Udemy", "Khan Academy", "Udacity"]
Output : "GeeksforGeeks" "Udemy"
Explanation : There are two common websites and index sum
of both is same.
Método ingenuo:
La idea es probar todas las sumas de índices desde 0 hasta la suma de tamaños. Para cada suma, verifique si hay pares con la suma dada. Una vez que encontramos uno o más pares, los imprimimos y volvemos.
C++
#include <bits/stdc++.h>
using namespace std;
// Function to print common strings with minimum index sum
void find(vector<string> list1, vector<string> list2)
{
vector<string> res; // resultant list
int max_possible_sum = list1.size() + list2.size() - 2;
// iterating over sum in ascending order
for (int sum = 0; sum <= max_possible_sum ; sum++)
{
// iterating over one list and check index
// (Corresponding to given sum) in other list
for (int i = 0; i <= sum; i++)
// put common strings in resultant list
if (i < list1.size() &&
(sum - i) < list2.size() &&
list1[i] == list2[sum - i])
res.push_back(list1[i]);
// if common string found then break as we are
// considering index sums in increasing order.
if (res.size() > 0)
break;
}
// print the resultant list
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
}
// Driver code
int main()
{
// Creating list1
vector<string> list1;
list1.push_back("GeeksforGeeks");
list1.push_back("Udemy");
list1.push_back("Coursera");
list1.push_back("edX");
// Creating list2
vector<string> list2;
list2.push_back("Codecademy");
list2.push_back("Khan Academy");
list2.push_back("GeeksforGeeks");
find(list1, list2);
return 0;
}
Java
import java.util.*;
class GFG
{
// Function to print common Strings with minimum index sum
static void find(Vector<String> list1, Vector<String> list2)
{
Vector<String> res = new Vector<>(); // resultant list
int max_possible_sum = list1.size() + list2.size() - 2;
// iterating over sum in ascending order
for (int sum = 0; sum <= max_possible_sum ; sum++)
{
// iterating over one list and check index
// (Corresponding to given sum) in other list
for (int i = 0; i <= sum; i++)
// put common Strings in resultant list
if (i < list1.size() &&
(sum - i) < list2.size() &&
list1.get(i) == list2.get(sum - i))
res.add(list1.get(i));
// if common String found then break as we are
// considering index sums in increasing order.
if (res.size() > 0)
break;
}
// print the resultant list
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i)+" ");
}
// Driver code
public static void main(String[] args)
{
// Creating list1
Vector<String> list1 = new Vector<>();
list1.add("GeeksforGeeks");
list1.add("Udemy");
list1.add("Coursera");
list1.add("edX");
// Creating list2
Vector<String> list2= new Vector<>();
list2.add("Codecademy");
list2.add("Khan Academy");
list2.add("GeeksforGeeks");
find(list1, list2);
}
}
// This code contributed by Rajput-Ji
Python3
# Function to print common strings
# with minimum index sum
def find(list1, list2):
res = [] # resultant list
max_possible_sum = len(list1) + len(list2) - 2
# iterating over sum in ascending order
for sum in range(max_possible_sum + 1):
# iterating over one list and check index
# (Corresponding to given sum) in other list
for i in range(sum + 1):
# put common strings in resultant list
if (i < len(list1) and
(sum - i) < len(list2) and
list1[i] == list2[sum - i]):
res.append(list1[i])
# if common string found then break as we are
# considering index sums in increasing order.
if (len(res) > 0):
break
# print the resultant list
for i in range(len(res)):
print(res[i], end = " ")
# Driver code
# Creating list1
list1 = []
list1.append("GeeksforGeeks")
list1.append("Udemy")
list1.append("Coursera")
list1.append("edX")
# Creating list2
list2 = []
list2.append("Codecademy")
list2.append("Khan Academy")
list2.append("GeeksforGeeks")
find(list1, list2)
# This code is contributed by Mohit Kumar
C#
using System;
using System.Collections.Generic;
class GFG
{
// Function to print common Strings with minimum index sum
static void find(List<String> list1, List<String> list2)
{
List<String> res = new List<String>(); // resultant list
int max_possible_sum = list1.Count + list2.Count - 2;
// iterating over sum in ascending order
for (int sum = 0; sum <= max_possible_sum ; sum++)
{
// iterating over one list and check index
// (Corresponding to given sum) in other list
for (int i = 0; i <= sum; i++)
// put common Strings in resultant list
if (i < list1.Count &&
(sum - i) < list2.Count &&
list1[i] == list2[sum - i])
res.Add(list1[i]);
// if common String found then break as we are
// considering index sums in increasing order.
if (res.Count > 0)
break;
}
// print the resultant list
for (int i = 0; i < res.Count; i++)
Console.Write(res[i]+" ");
}
// Driver code
public static void Main(String[] args)
{
// Creating list1
List<String> list1 = new List<String>();
list1.Add("GeeksforGeeks");
list1.Add("Udemy");
list1.Add("Coursera");
list1.Add("edX");
// Creating list2
List<String> list2= new List<String>();
list2.Add("Codecademy");
list2.Add("Khan Academy");
list2.Add("GeeksforGeeks");
find(list1, list2);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Function to print common Strings with minimum index sum
function find(list1, list2)
{
let res = []; // resultant list
let max_possible_sum = list1.length + list2.length - 2;
// iterating over sum in ascending order
for (let sum = 0; sum <= max_possible_sum ; sum++)
{
// iterating over one list and check index
// (Corresponding to given sum) in other list
for (let i = 0; i <= sum; i++)
// put common Strings in resultant list
if (i < list1.length &&
(sum - i) < list2.length &&
list1[i] == list2[sum - i])
res.push(list1[i]);
// if common String found then break as we are
// considering index sums in increasing order.
if (res.length > 0)
break;
}
// print the resultant list
for (let i = 0; i < res.length; i++)
document.write(res[i]+" ");
}
// Creating list1
let list1 = [];
list1.push("GeeksforGeeks");
list1.push("Udemy");
list1.push("Coursera");
list1.push("edX");
// Creating list2
let list2= [];
list2.push("Codecademy");
list2.push("Khan Academy");
list2.push("GeeksforGeeks");
find(list1, list2);
// This code is contributed by mukesh07.
</script>
Producción:
GeeksforGeeks
Complejidad de tiempo: O((l 1 +l 2 ) 2 *x), donde l 1 y l 2 son las longitudes de list1 y list2 respectivamente y x se refiere a la longitud de la string.
Espacio auxiliar: O(l*x), donde x se refiere a la longitud de la lista resultante y l es la longitud de la palabra de tamaño máximo.
Usando hash:
- Recorra list1 y cree una entrada para indexar cada elemento de list1 en una tabla hash.
- Recorra list2 y para cada elemento, verifique si el mismo elemento ya existe como una clave en el mapa. Si es así, significa que el elemento existe en ambas listas.
- Averigüe la suma de los índices correspondientes al elemento común en las dos listas. Si esta suma es menor que la suma mínima obtenida hasta ahora, actualice la lista resultante.
- Si la suma es igual a la suma mínima obtenida hasta ahora, coloque una entrada adicional correspondiente al elemento en list2 en la lista resultante.
C++
// Hashing based C++ program to find common elements
// with minimum index sum.
#include <bits/stdc++.h>
using namespace std;
// Function to print common strings with minimum index sum
void find(vector<string> list1, vector<string> list2)
{
// mapping strings to their indices
unordered_map<string, int> map;
for (int i = 0; i < list1.size(); i++)
map[list1[i]] = i;
vector<string> res; // resultant list
int minsum = INT_MAX;
for (int j = 0; j < list2.size(); j++)
{
if (map.count(list2[j]))
{
// If current sum is smaller than minsum
int sum = j + map[list2[j]];
if (sum < minsum)
{
minsum = sum;
res.clear();
res.push_back(list2[j]);
}
// if index sum is same then put this
// string in resultant list as well
else if (sum == minsum)
res.push_back(list2[j]);
}
}
// Print result
for (int i = 0; i < res.size(); i++)
cout << res[i] << " ";
}
// Driver code
int main()
{
// Creating list1
vector<string> list1;
list1.push_back("GeeksforGeeks");
list1.push_back("Udemy");
list1.push_back("Coursera");
list1.push_back("edX");
// Creating list2
vector<string> list2;
list2.push_back("Codecademy");
list2.push_back("Khan Academy");
list2.push_back("GeeksforGeeks");
find(list1, list2);
return 0;
}
Java
// Hashing based Java program to find common elements
// with minimum index sum.
import java.util.*;
class GFG
{
// Function to print common Strings with minimum index sum
static void find(Vector<String> list1, Vector<String> list2)
{
// mapping Strings to their indices
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < list1.size(); i++)
map.put(list1.get(i), i);
Vector<String> res = new Vector<String>(); // resultant list
int minsum = Integer.MAX_VALUE;
for (int j = 0; j < list2.size(); j++)
{
if (map.containsKey(list2.get(j)))
{
// If current sum is smaller than minsum
int sum = j + map.get(list2.get(j));
if (sum < minsum)
{
minsum = sum;
res.clear();
res.add(list2.get(j));
}
// if index sum is same then put this
// String in resultant list as well
else if (sum == minsum)
res.add(list2.get(j));
}
}
// Print result
for (int i = 0; i < res.size(); i++)
System.out.print(res.get(i) + " ");
}
// Driver code
public static void main(String[] args)
{
// Creating list1
Vector<String> list1 = new Vector<String>();
list1.add("GeeksforGeeks");
list1.add("Udemy");
list1.add("Coursera");
list1.add("edX");
// Creating list2
Vector<String> list2 = new Vector<String>();
list2.add("Codecademy");
list2.add("Khan Academy");
list2.add("GeeksforGeeks");
find(list1, list2);
}
}
// This code is contributed by PrinciRaj1992
Python3
# Hashing based Python3 program to find
# common elements with minimum index sum
import sys
# Function to print common strings
# with minimum index sum
def find(list1, list2):
# Mapping strings to their indices
Map = {}
for i in range(len(list1)):
Map[list1[i]] = i
# Resultant list
res = []
minsum = sys.maxsize
for j in range(len(list2)):
if list2[j] in Map:
# If current sum is smaller
# than minsum
Sum = j + Map[list2[j]]
if (Sum < minsum):
minsum = Sum
res.clear()
res.append(list2[j])
# If index sum is same then put this
# string in resultant list as well
else if (Sum == minsum):
res.append(list2[j])
# Print result
print(*res, sep = " ")
# Driver code
# Creating list1
list1 = []
list1.append("GeeksforGeeks")
list1.append("Udemy")
list1.append("Coursera")
list1.append("edX")
# Creating list2
list2 = []
list2.append("Codecademy")
list2.append("Khan Academy")
list2.append("GeeksforGeeks")
find(list1, list2)
# This code is contributed by avanitrachhadiya2155
C#
// Hashing based C# program to find common elements
// with minimum index sum.
using System;
using System.Collections.Generic;
class GFG
{
// Function to print common Strings with minimum index sum
static void find(List<String> list1, List<String> list2)
{
// mapping Strings to their indices
Dictionary<String, int> map = new Dictionary<String, int>();
for (int i = 0; i < list1.Count; i++)
map.Add(list1[i], i);
List<String> res = new List<String>(); // resultant list
int minsum = int.MaxValue;
for (int j = 0; j < list2.Count; j++)
{
if (map.ContainsKey(list2[j]))
{
// If current sum is smaller than minsum
int sum = j + map[list2[j]];
if (sum < minsum)
{
minsum = sum;
res.Clear();
res.Add(list2[j]);
}
// if index sum is same then put this
// String in resultant list as well
else if (sum == minsum)
res.Add(list2[j]);
}
}
// Print result
for (int i = 0; i < res.Count; i++)
Console.Write(res[i] + " ");
}
// Driver code
public static void Main(String[] args)
{
// Creating list1
List<String> list1 = new List<String>();
list1.Add("GeeksforGeeks");
list1.Add("Udemy");
list1.Add("Coursera");
list1.Add("edX");
// Creating list2
List<String> list2 = new List<String>();
list2.Add("Codecademy");
list2.Add("Khan Academy");
list2.Add("GeeksforGeeks");
find(list1, list2);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Hashing based Javascript program to
// find common elements with minimum
// index sum.
// Function to print common Strings
// with minimum index sum
function find(list1, list2)
{
// Mapping Strings to their indices
let map = new Map();
for(let i = 0; i < list1.length; i++)
map.set(list1[i], i);
// Resultant list
let res = [];
let minsum = Number.MAX_VALUE;
for(let j = 0; j < list2.length; j++)
{
if (map.has(list2[j]))
{
// If current sum is smaller than minsum
let sum = j + map.get(list2[j]);
if (sum < minsum)
{
minsum = sum;
res = [];
res.push(list2[j]);
}
// If index sum is same then put this
// String in resultant list as well
else if (sum == minsum)
res.push(list2[j]);
}
}
// Print result
for(let i = 0; i < res.length; i++)
document.write(res[i] + " ");
}
// Driver code
// Creating list1
let list1 = [];
list1.push("GeeksforGeeks");
list1.push("Udemy");
list1.push("Coursera");
list1.push("edX");
// Creating list2
let list2 = [];
list2.push("Codecademy");
list2.push("Khan Academy");
list2.push("GeeksforGeeks");
find(list1, list2);
// This code is contributed by rameshtravel07
</script>
Producción:
GeeksforGeeks
Complejidad de tiempo: O(l 1 +l 2 ), donde l 1 y l 2 son las longitudes de list1 y list2 respectivamente.
Espacio Auxiliar: O(l 1 *x), donde x se refiere a la longitud de la lista resultante y l es la longitud de la palabra de tamaño máximo.
Este artículo es una contribución de Aakash Pal . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA