Za dva niza se kaže da su potpuni ako pri ulančavanju sadrže svih 26 engleskih alfabeta. Na primjer, 'abcdefghi' i 'jklmnopqrstuvwxyz' su potpuni jer zajedno imaju sve znakove od 'a' do 'z'.
10 ml je koliko
Dana su nam dva skupa veličina n odnosno m i trebamo pronaći broj parova koji su potpuni ulančavanjem svakog niza iz skupa 1 u svaki niz iz skupa 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' Metoda 1 (Naivna metoda): Jednostavno rješenje je razmotriti sve parove nizova spojiti ih i zatim provjeriti ima li spojeni niz sve znakove od 'a' do 'z' pomoću frekvencijskog niza.
Implementacija:
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>
Izlaz
7
Vremenska složenost: O(n * m * k)
Pomoćni prostor: O(1)
promijeniti ime imenika linux
Metoda 2 (optimizirana metoda koja koristi manipulaciju bitovima): U ovoj metodi sažimamo niz frekvencija u cijeli broj. Svakom bitu tog cijelog broja dodjeljujemo znak i postavljamo ga na 1 kada znak pronađemo. Ovo izvodimo za sve žice u oba seta. Na kraju samo uspoređujemo dva cijela broja u skupovima i ako su pri kombiniranju svi bitovi postavljeni, oni čine potpuni par nizova.
Implementacija:
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>
Izlaz
7
Vremenska složenost: O(n*m) gdje je n veličina prvog skupa, a m veličina drugog skupa.
Pomoćni prostor: Na)
Ovaj je članak pridonio Rishabh Jain .