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".
codice grigio
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(set1set2nm): 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(set1set2nm) { 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(set1set2nm) { 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)
java mvc
Questo articolo è stato fornito da Rishabh Jain .