logo

Ištisų stygų poros dviejuose stygų rinkiniuose

Sakoma, kad dvi eilutės yra užbaigtos, jei jose yra visos 26 angliškos abėcėlės. Pavyzdžiui, „abcdefghi“ ir „jklmnopqrstuvwxyz“ yra užbaigti, nes jie kartu turi visus simbolius nuo „a“ iki „z“. 

nepakeičiamas sąrašas

Mums suteikiami du atitinkamai n ir m dydžių rinkiniai ir turime rasti porų, kurios yra užbaigtos, sujungdami kiekvieną eilutę iš 1 rinkinio į kiekvieną eilutę iš 2 rinkinio, skaičių.



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'

1 metodas (naivus metodas): Paprastas sprendimas yra apsvarstyti, kaip visos eilučių poros jas sujungia, o tada naudojant dažnių masyvą patikrinti, ar sujungtoje eilutėje yra visi simboliai nuo „a“ iki „z“.  

Įgyvendinimas:

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> 

Išvestis
7

Laiko sudėtingumas: O(n * m * k)
Pagalbinė erdvė: O(1)



2 metodas (optimizuotas metodas naudojant bitų manipuliavimą): Šiuo metodu dažnių masyvą suspaudžiame į sveikąjį skaičių. Kiekvienam šio sveikojo skaičiaus bitui priskiriame simbolį ir nustatome jį į 1, kai randame simbolį. Tai atliekame visoms abiejų rinkinių stygoms. Galiausiai mes tiesiog palyginame du sveikuosius skaičius rinkiniuose ir, sujungus visus bitus, jie sudaro pilną eilučių porą.

Įgyvendinimas:

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> 

Išvestis
7

Laiko sudėtingumas: O(n*m) kur n yra pirmosios aibės dydis, o m yra antrosios aibės dydis.
Pagalbinė erdvė: O(n)



prisijungti prie duomenų bazės java

Prie šio straipsnio prisidėjo Rishabh Jain .