Dada una array s[] de N strings. La tarea es encontrar el número de pares de índices (i, j) tales que s[i] es un anagrama de s[j] .
Ejemplos:
Entrada: s[] = {“aaab”, “aaba”, “cde”, “dec”}
Salida: 2
(“aaab”, “aaba”) y (“cde”, “dec”) son los únicos pares válidos .Entrada: s[] = {“ab”, “bc”, “cd”}
Salida: 0
Enfoque: un enfoque eficiente es ordenar cada string y aumentar el recuento de la misma en un mapa . Para cada string en el mapa, si k es su cuenta, entonces (k * (k – 1)) / 2 es el número de pares válidos.
A continuación se muestra la implementación del enfoque anterior:
C++
// CPP program to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
#include <bits/stdc++.h>
using namespace std;
// Function to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
int anagram_pairs(vector<string> s, int n)
{
// To store count of strings
map<string, int> mp;
// Traverse all strings and store in the map
for (int i = 0; i < n; i++) {
// Sort the string
sort(s[i].begin(), s[i].end());
// Store in the map
mp[s[i]]++;
}
// To store the number of pairs
int ans = 0;
// Traverse through the map
for (auto i = mp.begin(); i != mp.end(); i++) {
int k = i->second;
// Count the pairs for each string
ans += (k * (k - 1)) / 2;
}
// Return the required answer
return ans;
}
// Driver code
int main()
{
vector<string> s = { "aaab", "aaba", "baaa",
"cde", "dec" };
int n = s.size();
// Function call
cout << anagram_pairs(s, n);
return 0;
}
Java
// Java program to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
import java.util.*;
class GFG
{
// Function to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
static int anagram_pairs(String []s, int n)
{
// To store count of strings
Map<String, Integer> mp = new HashMap<>();
// Traverse all strings and store in the map
for (int i = 0; i < n; i++)
{
// Sort the string
char []chArr = s[i].toCharArray();
Arrays.sort(chArr);
s[i] = new String(chArr);
// Store in the map
if(mp.containsKey(s[i]))
{
mp.put(s[i], mp.get(s[i]) + 1);
}
else
{
mp.put(s[i], 1);
}
}
// To store the number of pairs
int ans = 0;
// Traverse through the map
for (Map.Entry<String,
Integer> i : mp.entrySet())
{
int k = i.getValue();
// Count the pairs for each string
ans += (k * (k - 1)) / 2;
}
// Return the required answer
return ans;
}
// Driver code
public static void main(String []args)
{
String [] s = { "aaab", "aaba", "baaa",
"cde", "dec" };
int n = s.length;
// Function call
System.out.println(anagram_pairs(s, n));
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 implementation to find # number of pairs of integers i, j # such that s[i] is an anagram of s[j]. # Function to find number of pairs of integers # i, j such that s[i] is an anagram of s[j]. def anagram_pairs(s, n): # To store the count of sorted strings mp = dict() # Traverse all strings and store in the map for i in range(n): # Sort the string temp_str = "".join(sorted(s[i])) # If string exists in map, increment count # Else create key value pair with count = 1 if temp_str in mp: mp[temp_str] += 1 else: mp[temp_str] = 1 # To store the number of pairs ans = 0 # Traverse through the map for k in mp.values(): # Count the pairs for each string ans += (k * (k - 1)) // 2 # Return the required answer return ans # Driver code if __name__ == "__main__": s = ["aaab", "aaba", "baaa", "cde", "dec"] n = len(s) print(anagram_pairs(s, n)) # This code is contributed by AnkitRai01
C#
// C# program to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
using System;
using System.Collections.Generic;
class GFG
{
// Function to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
static int anagram_pairs(String []s, int n)
{
// To store count of strings
Dictionary<String,
int> mp = new Dictionary<String,
int>();
// Traverse all strings and store in the map
for (int i = 0; i < n; i++)
{
// Sort the string
char []chArr = s[i].ToCharArray();
Array.Sort(chArr);
s[i] = new String(chArr);
// Store in the map
if(mp.ContainsKey(s[i]))
{
mp[s[i]] = mp[s[i]] + 1;
}
else
{
mp.Add(s[i], 1);
}
}
// To store the number of pairs
int ans = 0;
// Traverse through the map
foreach (KeyValuePair<String,
int> i in mp)
{
int k = i.Value;
// Count the pairs for each string
ans += (k * (k - 1)) / 2;
}
// Return the required answer
return ans;
}
// Driver code
public static void Main(String []args)
{
String [] s = { "aaab", "aaba", "baaa",
"cde", "dec" };
int n = s.Length;
// Function call
Console.WriteLine(anagram_pairs(s, n));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
// Function to find number of pairs of integers
// i, j such that s[i] is an anagram of s[j].
function anagram_pairs(s, n)
{
// To store count of strings
let mp = new Map();
// Traverse all strings and store in the map
for (let i = 0; i < n; i++) {
// Sort the string
let chArr = s[i].split("");
chArr.sort();
s[i] = chArr.join("");
// Store in the map
if(mp.has(s[i])){
mp.set(s[i], mp.get(s[i]) + 1)
}else{
mp.set(s[i], 1)
}
}
// To store the number of pairs
let ans = 0;
// Traverse through the map
for (let i of mp) {
let k = i[1];
// Count the pairs for each string
ans += Math.floor((k * (k - 1)) / 2);
}
// Return the required answer
return ans;
}
// Driver code
let s = [ "aaab", "aaba", "baaa", "cde", "dec" ];
let n = s.length;
// Function call
document.write(anagram_pairs(s, n));
// This code is contributed by _saurabh_jaiswal
</script>
Producción:
4
Complejidad de tiempo: O(n 2 * logn)
Espacio Auxiliar: O(n)
Publicación traducida automáticamente
Artículo escrito por pawan_asipu y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA