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>
Producción:
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