Dada una array de strings arr[] . La tarea es encontrar el conteo de pares desordenados de strings (arr[i], arr[j]) , que en la concatenación incluye cada carácter de la string “string” al menos una vez.
Ejemplos:
Entrada: arr[] = { “s”, “ng”, “stri”}
Salida: 1
(arr[1], arr[2]) es el único par que en la concatenación
contendrá todos los caracteres de la string “string”
es decir, arr[1] + arr[2] = “ngstri”Entrada: arr[] = { “stri”, “ing”, “string” }
Salida: 3
Enfoque: almacene las strings dadas como máscaras de bits, es decir, una string «srin» se almacenará como 101110 ya que faltan ‘t’ y ‘g’ , por lo que su bit correspondiente será 0 . Ahora, cree una array de tamaño 64 , que es el valor máximo posible de las máscaras de bits obtenidas (0 (000000) a 63 (111111)) . Ahora, el problema se reduce a encontrar el conteo de pares de estas máscaras de bits que dan 63 (111111 en binario) como su valor OR.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach #include <bits/stdc++.h> using namespace std; #define MAX 64 // Function to return the bitmask for the string int getBitmask(string s) { int temp = 0; for (int j = 0; j < s.length(); j++) { if (s[j] == 's') { temp = temp | (1); } else if (s[j] == 't') { temp = temp | (2); } else if (s[j] == 'r') { temp = temp | (4); } else if (s[j] == 'i') { temp = temp | (8); } else if (s[j] == 'n') { temp = temp | (16); } else if (s[j] == 'g') { temp = temp | (32); } } return temp; } // Function to return the count of pairs int countPairs(string arr[], int n) { // bitMask[i] will store the count of strings // from the array whose bitmask is i int bitMask[MAX] = { 0 }; for (int i = 0; i < n; i++) bitMask[getBitmask(arr[i])]++; // To store the count of pairs int cnt = 0; for (int i = 0; i < MAX; i++) { for (int j = i; j < MAX; j++) { // MAX - 1 = 63 i.e. 111111 in binary if ((i | j) == (MAX - 1)) { // arr[i] cannot make s pair with itself // i.e. (arr[i], arr[i]) if (i == j) cnt += ((bitMask[i] * bitMask[i] - 1) / 2); else cnt += (bitMask[i] * bitMask[j]); } } } return cnt; } // Driver code int main() { string arr[] = { "strrr", "string", "gstrin" }; int n = sizeof(arr) / sizeof(arr[0]); cout << countPairs(arr, n); return 0; }
Java
// Java implementation of the // above approach class GFG { static int MAX = 64; // Function to return the bitmask for the string static int getBitmask(char[] s) { int temp = 0; for (int j = 0; j < s.length; j++) { switch (s[j]) { case 's': temp = temp | (1); break; case 't': temp = temp | (2); break; case 'r': temp = temp | (4); break; case 'i': temp = temp | (8); break; case 'n': temp = temp | (16); break; case 'g': temp = temp | (32); break; default: break; } } return temp; } // Function to return the count of pairs static int countPairs(String arr[], int n) { // bitMask[i] will store the count of strings // from the array whose bitmask is i int []bitMask = new int[MAX]; for (int i = 0; i < n; i++) bitMask[getBitmask(arr[i].toCharArray())]++; // To store the count of pairs int cnt = 0; for (int i = 0; i < MAX; i++) { for (int j = i; j < MAX; j++) { // MAX - 1 = 63 i.e. 111111 in binary if ((i | j) == (MAX - 1)) { // arr[i] cannot make s pair with itself // i.e. (arr[i], arr[i]) if (i == j) cnt += ((bitMask[i] * bitMask[i] - 1) / 2); else cnt += (bitMask[i] * bitMask[j]); } } } return cnt; } // Driver code public static void main(String[] args) { String arr[] = { "strrr", "string", "gstrin" }; int n = arr.length; System.out.println(countPairs(arr, n)); } } /* This code contributed by PrinciRaj1992 */
Python3
# Python3 implementation of the approach MAX = 64 # Function to return the bitmask # for the string def getBitmask(s): temp = 0 for j in range(len(s)): if (s[j] == 's'): temp = temp | 1 elif (s[j] == 't'): temp = temp | 2 elif (s[j] == 'r'): temp = temp | 4 elif (s[j] == 'i'): temp = temp | 8 elif (s[j] == 'n'): temp = temp | 16 elif (s[j] == 'g'): temp = temp | 32 return temp # Function to return the count of pairs def countPairs(arr, n): # bitMask[i] will store the count of strings # from the array whose bitmask is i bitMask = [0 for i in range(MAX)] for i in range(n): bitMask[getBitmask(arr[i])] += 1 # To store the count of pairs cnt = 0 for i in range(MAX): for j in range(i, MAX): # MAX - 1 = 63 i.e. 111111 in binary if ((i | j) == (MAX - 1)): # arr[i] cannot make s pair with itself # i.e. (arr[i], arr[i]) if (i == j): cnt += ((bitMask[i] * bitMask[i] - 1) // 2) else: cnt += (bitMask[i] * bitMask[j]) return cnt # Driver code arr = ["strrr", "string", "gstrin"] n = len(arr) print(countPairs(arr, n)) # This code is contributed by mohit kumar
C#
// C# implementation of the // above approach using System; using System.Collections.Generic; class GFG { static int MAX = 64; // Function to return the bitmask for the string static int getBitmask(char[] s) { int temp = 0; for (int j = 0; j < s.Length; j++) { switch (s[j]) { case 's': temp = temp | (1); break; case 't': temp = temp | (2); break; case 'r': temp = temp | (4); break; case 'i': temp = temp | (8); break; case 'n': temp = temp | (16); break; case 'g': temp = temp | (32); break; default: break; } } return temp; } // Function to return the count of pairs static int countPairs(String []arr, int n) { // bitMask[i] will store the count of strings // from the array whose bitmask is i int []bitMask = new int[MAX]; for (int i = 0; i < n; i++) bitMask[getBitmask(arr[i].ToCharArray())]++; // To store the count of pairs int cnt = 0; for (int i = 0; i < MAX; i++) { for (int j = i; j < MAX; j++) { // MAX - 1 = 63 i.e. 111111 in binary if ((i | j) == (MAX - 1)) { // arr[i] cannot make s pair with itself // i.e. (arr[i], arr[i]) if (i == j) cnt += ((bitMask[i] * bitMask[i] - 1) / 2); else cnt += (bitMask[i] * bitMask[j]); } } } return cnt; } // Driver code public static void Main(String[] args) { String []arr = { "strrr", "string", "gstrin" }; int n = arr.Length; Console.WriteLine(countPairs(arr, n)); } } // This code has been contributed by 29AjayKumar
PHP
<?php // PHP implementation of the approach $MAX = 64; // Function to return the bitmask for the string function getBitmask($s) { $temp = 0; for ($j = 0; $j < strlen($s); $j++) { if ($s[$j] == 's') { $temp = $temp | (1); } else if ($s[$j] == 't') { $temp = $temp | (2); } else if ($s[$j] == 'r') { $temp = $temp | (4); } else if ($s[$j] == 'i') { $temp = $temp | (8); } else if ($s[$j] == 'n') { $temp = $temp | (16); } else if ($s[$j] == 'g') { $temp = $temp | (32); } } return $temp; } // Function to return the count of pairs function countPairs($arr, $n) { // bitMask[i] will store the count of strings // from the array whose bitmask is i $bitMask = array_fill(0, $GLOBALS['MAX'], 0); for ($i = 0; $i < $n; $i++) $bitMask[getBitmask($arr[$i])]++; // To store the count of pairs $cnt = 0; for ($i = 0; $i < $GLOBALS['MAX']; $i++) { for ($j = $i; $j < $GLOBALS['MAX']; $j++) { // MAX - 1 = 63 i.e. 111111 in binary if (($i | $j) == ($GLOBALS['MAX'] - 1)) { // arr[i] cannot make s pair with itself // i.e. (arr[i], arr[i]) if ($i == $j) $cnt += floor(($bitMask[$i] * $bitMask[$i] - 1) / 2); else $cnt += ($bitMask[$i] * $bitMask[$j]); } } } return $cnt; } // Driver code $arr = array( "strrr", "string", "gstrin" ); $n = count($arr); echo countPairs($arr, $n); // This code is contributed by Ryuga ?>
Javascript
<script> // JavaScript implementation of the // above approach const MAX = 64; // Function to return the bitmask for the string function getBitmask(s) { var temp = 0; for (var j = 0; j < s.length; j++) { switch (s[j]) { case "s": temp = temp | 1; break; case "t": temp = temp | 2; break; case "r": temp = temp | 4; break; case "i": temp = temp | 8; break; case "n": temp = temp | 16; break; case "g": temp = temp | 32; break; default: break; } } return temp; } // Function to return the count of pairs function countPairs(arr, n) { // bitMask[i] will store the count of strings // from the array whose bitmask is i var bitMask = new Array(MAX).fill(0); for (var i = 0; i < n; i++) bitMask[getBitmask(arr[i].split(""))]++; // To store the count of pairs var cnt = 0; for (var i = 0; i < MAX; i++) { for (var j = i; j < MAX; j++) { // MAX - 1 = 63 i.e. 111111 in binary if ((i | j) === MAX - 1) { // arr[i] cannot make s pair with itself // i.e. (arr[i], arr[i]) if (i === j) cnt += parseInt((bitMask[i] * bitMask[i] - 1) / 2); else cnt += bitMask[i] * bitMask[j]; } } } return cnt; } // Driver code var arr = ["strrr", "string", "gstrin"]; var n = arr.length; document.write(countPairs(arr, n)); </script>
3
Complejidad de tiempo: O(n * |s| + MAX 2 )
Espacio Auxiliar: O(MAX)
Publicación traducida automáticamente
Artículo escrito por himanshu_rathore y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA