logo

2 つの文字列セット内の完全な文字列のペア

2 つの文字列は、連結時に 26 個の英語アルファベットすべてが含まれている場合に完全であると言われます。たとえば、「abcdefghi」と「jklmnopqrstuvwxyz」は、「a」から「z」までのすべての文字が一緒に含まれるため、完全になります。 

SQLのランダムな順序

それぞれサイズ n と m の 2 つのセットが与えられ、セット 1 の各文字列をセット 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'

方法 1 (単純な方法): 簡単な解決策は、文字列のすべてのペアが連結されているとみなして、頻度配列を使用して連結された文字列に「a」から「z」までのすべての文字が含まれているかどうかを確認することです。  

実装:

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> 

出力
7

時間計算量: O(n * m * k)
補助スペース: O(1)



タイプスクリプトでのマップ

方法 2 (ビット操作を使用した最適化された方法): この方法では、周波数配列を整数に圧縮します。その整数の各ビットに文字を割り当て、その文字が見つかったときに 1 に設定します。両方のセット内のすべての文字列に対してこれを実行します。最後に、セット内の 2 つの整数を比較するだけです。すべてのビットを組み合わせて設定されていれば、完全な文字列ペアが形成されます。

実装:

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> 

出力
7

時間計算量: O(n*m) ここで、n は最初のセットのサイズ、m は 2 番目のセットのサイズです。
補助スペース: の上)



この記事は次の寄稿者です リシャブ・ジャイン 。