Coppie di corde complete in due set di corde
Due stringhe si dicono complete se concatenate contengono tutti i 26 alfabeti inglesi. Ad esempio, "abcdefghi" e "jklmnopqrstuvwxyz" sono completi poiché insieme contengono tutti i caratteri dalla "a" alla "z".
Ci vengono dati due insiemi di dimensioni n e m rispettivamente e dobbiamo trovare il numero di coppie complete concatenando ciascuna stringa dell'insieme 1 con ciascuna stringa dell'insieme 2.
Input : set1[] = {'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc'} set2[] = {'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz'} Output : 7 The total complete pairs that are forming are: 'abcdefghijklmnopqrstuvwxyz' 'abcdefghabcdefghijklmnopqrstuvwxyz' 'abcdefghdefghijklmnopqrstuvwxyz' 'geeksforgeeksabcdefghijklmnopqrstuvwxyz' 'lmnopqrstabcdefghijklmnopqrstuvwxyz' 'abcabcdefghijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' Metodo 1 (metodo ingenuo): Una soluzione semplice è considerare tutte le coppie di stringhe concatenarle e quindi verificare se la stringa concatenata contiene tutti i caratteri da "a" a "z" utilizzando un array di frequenze.
Attuazione:
C++ // C++ implementation for find pairs of complete // strings. #include using namespace std ; // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] int countCompletePairs ( string set1 [] string set2 [] int n int m ) { int result = 0 ; // Consider all pairs of both strings for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // Create a concatenation of current pair string concat = set1 [ i ] + set2 [ j ]; // Compute frequencies of all characters // in the concatenated string. int frequency [ 26 ] = { 0 }; for ( int k = 0 ; k < concat . length (); k ++ ) frequency [ concat [ k ] - 'a' ] ++ ; // If frequency of any character is not // greater than 0 then this pair is not // complete. int i ; for ( i = 0 ; i < 26 ; i ++ ) if ( frequency [ i ] < 1 ) break ; if ( i == 26 ) result ++ ; } } return result ; } // Driver code int main () { string set1 [] = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; string set2 [] = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = sizeof ( set1 ) / sizeof ( set1 [ 0 ]); int m = sizeof ( set2 ) / sizeof ( set2 [ 0 ]); cout < < countCompletePairs ( set1 set2 n m ); return 0 ; }
Java // Java implementation for find pairs of complete // strings. class GFG { // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] static int countCompletePairs ( String set1 [] String set2 [] int n int m ) { int result = 0 ; // Consider all pairs of both strings for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // Create a concatenation of current pair String concat = set1 [ i ] + set2 [ j ] ; // Compute frequencies of all characters // in the concatenated String. int frequency [] = new int [ 26 ] ; for ( int k = 0 ; k < concat . length (); k ++ ) { frequency [ concat . charAt ( k ) - 'a' ]++ ; } // If frequency of any character is not // greater than 0 then this pair is not // complete. int k ; for ( k = 0 ; k < 26 ; k ++ ) { if ( frequency [ k ] < 1 ) { break ; } } if ( k == 26 ) { result ++ ; } } } return result ; } // Driver code static public void main ( String [] args ) { String set1 [] = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; String set2 [] = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = set1 . length ; int m = set2 . length ; System . out . println ( countCompletePairs ( set1 set2 n m )); } } // This code is contributed by PrinciRaj19992
Python3 # Python3 implementation for find pairs of complete # strings. # Returns count of complete pairs from set[0..n-1] # and set2[0..m-1] def countCompletePairs ( set1 set2 n m ): result = 0 # Consider all pairs of both strings for i in range ( n ): for j in range ( m ): # Create a concatenation of current pair concat = set1 [ i ] + set2 [ j ] # Compute frequencies of all characters # in the concatenated String. frequency = [ 0 for i in range ( 26 )] for k in range ( len ( concat )): frequency [ ord ( concat [ k ]) - ord ( 'a' )] += 1 # If frequency of any character is not # greater than 0 then this pair is not # complete. k = 0 while ( k < 26 ): if ( frequency [ k ] < 1 ): break k += 1 if ( k == 26 ): result += 1 return result # Driver code set1 = [ 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' ] set2 = [ 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' ] n = len ( set1 ) m = len ( set2 ) print ( countCompletePairs ( set1 set2 n m )) # This code is contributed by shinjanpatra
C# // C# implementation for find pairs of complete // strings. using System ; class GFG { // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] static int countCompletePairs ( string [] set1 string [] set2 int n int m ) { int result = 0 ; // Consider all pairs of both strings for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // Create a concatenation of current pair string concat = set1 [ i ] + set2 [ j ]; // Compute frequencies of all characters // in the concatenated String. int [] frequency = new int [ 26 ]; for ( int k = 0 ; k < concat . Length ; k ++ ) { frequency [ concat [ k ] - 'a' ] ++ ; } // If frequency of any character is not // greater than 0 then this pair is not // complete. int l ; for ( l = 0 ; l < 26 ; l ++ ) { if ( frequency [ l ] < 1 ) { break ; } } if ( l == 26 ) { result ++ ; } } } return result ; } // Driver code static public void Main () { string [] set1 = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; string [] set2 = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = set1 . Length ; int m = set2 . Length ; Console . Write ( countCompletePairs ( set1 set2 n m )); } } // This article is contributed by Ita_c.
JavaScript < script > // Javascript implementation for find pairs of complete // strings. // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] function countCompletePairs ( set1 set2 n m ) { let result = 0 ; // Consider all pairs of both strings for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { // Create a concatenation of current pair let concat = set1 [ i ] + set2 [ j ]; // Compute frequencies of all characters // in the concatenated String. let frequency = new Array ( 26 ); for ( let i = 0 ; i < 26 ; i ++ ) { frequency [ i ] = 0 ; } for ( let k = 0 ; k < concat . length ; k ++ ) { frequency [ concat [ k ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 )] ++ ; } // If frequency of any character is not // greater than 0 then this pair is not // complete. let k ; for ( k = 0 ; k < 26 ; k ++ ) { if ( frequency [ k ] < 1 ) { break ; } } if ( k == 26 ) { result ++ ; } } } return result ; } // Driver code let set1 = [ 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' ]; let set2 = [ 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' ] let n = set1 . length ; let m = set2 . length ; document . write ( countCompletePairs ( set1 set2 n m )); // This code is contributed by avanitrachhadiya2155 < /script>
Produzione
7
Complessità temporale: O(n * m * k)
Spazio ausiliario: O(1)
Metodo 2 (metodo ottimizzato utilizzando la manipolazione dei bit): In questo metodo comprimiamo l'array di frequenza in un numero intero. Assegniamo a ciascun bit di quell'intero un carattere e lo impostiamo a 1 quando il carattere viene trovato. Eseguiamo questa operazione per tutte le corde di entrambi i set. Alla fine confrontiamo semplicemente i due interi negli insiemi e se combinando tutti i bit vengono impostati formano una coppia di stringhe completa.
Attuazione:
C++14 // C++ program to find count of complete pairs #include using namespace std ; // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] int countCompletePairs ( string set1 [] string set2 [] int n int m ) { int result = 0 ; // con_s1[i] is going to store an integer whose // set bits represent presence/absence of characters // in string set1[i]. // Similarly con_s2[i] is going to store an integer // whose set bits represent presence/absence of // characters in string set2[i] int con_s1 [ n ] con_s2 [ m ]; // Process all strings in set1[] for ( int i = 0 ; i < n ; i ++ ) { // initializing all bits to 0 con_s1 [ i ] = 0 ; for ( int j = 0 ; j < set1 [ i ]. length (); j ++ ) { // Setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s1 [ i ] = con_s1 [ i ] | ( 1 < < ( set1 [ i ][ j ] - 'a' )); } } // Process all strings in set2[] for ( int i = 0 ; i < m ; i ++ ) { // initializing all bits to 0 con_s2 [ i ] = 0 ; for ( int j = 0 ; j < set2 [ i ]. length (); j ++ ) { // setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s2 [ i ] = con_s2 [ i ] | ( 1 < < ( set2 [ i ][ j ] - 'a' )); } } // assigning a variable whose all 26 (0..25) // bits are set to 1 long long complete = ( 1 < < 26 ) - 1 ; // Now consider every pair of integer in con_s1[] // and con_s2[] and check if the pair is complete. for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if all bits are set the strings are // complete! if (( con_s1 [ i ] | con_s2 [ j ]) == complete ) result ++ ; } } return result ; } // Driver code int main () { string set1 [] = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; string set2 [] = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = sizeof ( set1 ) / sizeof ( set1 [ 0 ]); int m = sizeof ( set2 ) / sizeof ( set2 [ 0 ]); cout < < countCompletePairs ( set1 set2 n m ); return 0 ; }
Java // Java program to find count of complete pairs class GFG { // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] static int countCompletePairs ( String set1 [] String set2 [] int n int m ) { int result = 0 ; // con_s1[i] is going to store an integer whose // set bits represent presence/absence of characters // in string set1[i]. // Similarly con_s2[i] is going to store an integer // whose set bits represent presence/absence of // characters in string set2[i] int [] con_s1 = new int [ n ] ; int [] con_s2 = new int [ m ] ; // Process all strings in set1[] for ( int i = 0 ; i < n ; i ++ ) { // initializing all bits to 0 con_s1 [ i ] = 0 ; for ( int j = 0 ; j < set1 [ i ] . length (); j ++ ) { // Setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s1 [ i ] = con_s1 [ i ] | ( 1 < < ( set1 [ i ] . charAt ( j ) - 'a' )); } } // Process all strings in set2[] for ( int i = 0 ; i < m ; i ++ ) { // initializing all bits to 0 con_s2 [ i ] = 0 ; for ( int j = 0 ; j < set2 [ i ] . length (); j ++ ) { // setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s2 [ i ] = con_s2 [ i ] | ( 1 < < ( set2 [ i ] . charAt ( j ) - 'a' )); } } // assigning a variable whose all 26 (0..25) // bits are set to 1 long complete = ( 1 < < 26 ) - 1 ; // Now consider every pair of integer in con_s1[] // and con_s2[] and check if the pair is complete. for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if all bits are set the strings are // complete! if (( con_s1 [ i ] | con_s2 [ j ] ) == complete ) { result ++ ; } } } return result ; } // Driver code public static void main ( String args [] ) { String set1 [] = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; String set2 [] = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = set1 . length ; int m = set2 . length ; System . out . println ( countCompletePairs ( set1 set2 n m )); } } // This code contributed by Rajput-Ji
C# // C# program to find count of complete pairs using System ; class GFG { // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] static int countCompletePairs ( String [] set1 String [] set2 int n int m ) { int result = 0 ; // con_s1[i] is going to store an integer whose // set bits represent presence/absence of characters // in string set1[i]. // Similarly con_s2[i] is going to store an integer // whose set bits represent presence/absence of // characters in string set2[i] int [] con_s1 = new int [ n ]; int [] con_s2 = new int [ m ]; // Process all strings in set1[] for ( int i = 0 ; i < n ; i ++ ) { // initializing all bits to 0 con_s1 [ i ] = 0 ; for ( int j = 0 ; j < set1 [ i ]. Length ; j ++ ) { // Setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s1 [ i ] = con_s1 [ i ] | ( 1 < < ( set1 [ i ][ j ] - 'a' )); } } // Process all strings in set2[] for ( int i = 0 ; i < m ; i ++ ) { // initializing all bits to 0 con_s2 [ i ] = 0 ; for ( int j = 0 ; j < set2 [ i ]. Length ; j ++ ) { // setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s2 [ i ] = con_s2 [ i ] | ( 1 < < ( set2 [ i ][ j ] - 'a' )); } } // assigning a variable whose all 26 (0..25) // bits are set to 1 long complete = ( 1 < < 26 ) - 1 ; // Now consider every pair of integer in con_s1[] // and con_s2[] and check if the pair is complete. for ( int i = 0 ; i < n ; i ++ ) { for ( int j = 0 ; j < m ; j ++ ) { // if all bits are set the strings are // complete! if (( con_s1 [ i ] | con_s2 [ j ]) == complete ) { result ++ ; } } } return result ; } // Driver code public static void Main ( String [] args ) { String [] set1 = { 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' }; String [] set2 = { 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' }; int n = set1 . Length ; int m = set2 . Length ; Console . WriteLine ( countCompletePairs ( set1 set2 n m )); } } // This code has been contributed by 29AjayKumar
Python3 # Python3 program to find count of complete pairs # Returns count of complete pairs from set[0..n-1] # and set2[0..m-1] def countCompletePairs ( set1 set2 n m ): result = 0 # con_s1[i] is going to store an integer whose # set bits represent presence/absence of characters # in set1[i]. # Similarly con_s2[i] is going to store an integer # whose set bits represent presence/absence of # characters in set2[i] con_s1 con_s2 = [ 0 ] * n [ 0 ] * m # Process all strings in set1[] for i in range ( n ): # initializing all bits to 0 con_s1 [ i ] = 0 for j in range ( len ( set1 [ i ])): # Setting the ascii code of char s[i][j] # to 1 in the compressed integer. con_s1 [ i ] = con_s1 [ i ] | ( 1 < < ( ord ( set1 [ i ][ j ]) - ord ( 'a' ))) # Process all strings in set2[] for i in range ( m ): # initializing all bits to 0 con_s2 [ i ] = 0 for j in range ( len ( set2 [ i ])): # setting the ascii code of char s[i][j] # to 1 in the compressed integer. con_s2 [ i ] = con_s2 [ i ] | ( 1 < < ( ord ( set2 [ i ][ j ]) - ord ( 'a' ))) # assigning a variable whose all 26 (0..25) # bits are set to 1 complete = ( 1 < < 26 ) - 1 # Now consider every pair of integer in con_s1[] # and con_s2[] and check if the pair is complete. for i in range ( n ): for j in range ( m ): # if all bits are set the strings are # complete! if (( con_s1 [ i ] | con_s2 [ j ]) == complete ): result += 1 return result # Driver code if __name__ == '__main__' : set1 = [ 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' ] set2 = [ 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' ] n = len ( set1 ) m = len ( set2 ) print ( countCompletePairs ( set1 set2 n m )) # This code is contributed by mohit kumar 29
JavaScript < script > // Javascript program to find count of complete pairs // Returns count of complete pairs from set[0..n-1] // and set2[0..m-1] function countCompletePairs ( set1 set2 n m ) { let result = 0 ; // con_s1[i] is going to store an integer whose // set bits represent presence/absence of characters // in string set1[i]. // Similarly con_s2[i] is going to store an integer // whose set bits represent presence/absence of // characters in string set2[i] let con_s1 = new Array ( n ); let con_s2 = new Array ( m ); // Process all strings in set1[] for ( let i = 0 ; i < n ; i ++ ) { // initializing all bits to 0 con_s1 [ i ] = 0 ; for ( let j = 0 ; j < set1 [ i ]. length ; j ++ ) { // Setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s1 [ i ] = con_s1 [ i ] | ( 1 < < ( set1 [ i ][ j ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 ))); } } // Process all strings in set2[] for ( let i = 0 ; i < m ; i ++ ) { // initializing all bits to 0 con_s2 [ i ] = 0 ; for ( let j = 0 ; j < set2 [ i ]. length ; j ++ ) { // setting the ascii code of char s[i][j] // to 1 in the compressed integer. con_s2 [ i ] = con_s2 [ i ] | ( 1 < < ( set2 [ i ][ j ]. charCodeAt ( 0 ) - 'a' . charCodeAt ( 0 ))); } } // assigning a variable whose all 26 (0..25) // bits are set to 1 let complete = ( 1 < < 26 ) - 1 ; // Now consider every pair of integer in con_s1[] // and con_s2[] and check if the pair is complete. for ( let i = 0 ; i < n ; i ++ ) { for ( let j = 0 ; j < m ; j ++ ) { // if all bits are set the strings are // complete! if (( con_s1 [ i ] | con_s2 [ j ]) == complete ) { result ++ ; } } } return result ; } // Driver code let set1 = [ 'abcdefgh' 'geeksforgeeks' 'lmnopqrst' 'abc' ]; let set2 = [ 'ijklmnopqrstuvwxyz' 'abcdefghijklmnopqrstuvwxyz' 'defghijklmnopqrstuvwxyz' ] let n = set1 . length ; let m = set2 . length ; document . write ( countCompletePairs ( set1 set2 n m )); // This code is contributed by avanitrachhadiya2155 < /script>
Produzione
7
Complessità temporale: O(n*m) dove n è la dimensione del primo insieme e m è la dimensione del secondo insieme.
Spazio ausiliario: SU)
Questo articolo è stato fornito da Rishabh Jain .
