Рубрики

Пары полных строк в двух наборах строк

Говорят, что две строки являются полными, если при объединении они содержат все 26 английских алфавитов. Например, «abcdefghi» и «jklmnopqrstuvwxyz» завершены, поскольку они вместе содержат все символы от «a» до «z».
Нам даны два набора размеров n и m соответственно, и нам нужно найти количество пар, которые являются полными при конкатенации каждой строки из набора 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 ++ реализация для поиска пар завершенных
// строки.
#include <iostream>

using namespace std;

  
// Возвращает количество полных пар из набора [0..n-1]
// и set2 [0..m-1]

int countCompletePairs(string set1[], string set2[],

                       int n, int m)

{

    int result = 0;

  

    // Рассмотрим все пары обеих строк

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            // Создать конкатенацию текущей пары

            string concat = set1[i] + set2[j];

  

            // Вычисляем частоты всех символов

            // в объединенной строке.

            int frequency[26] = { 0 };

            for (int k = 0; k < concat.length(); k++)

                frequency[concat[k] - 'a']++;

  

            // Если частота любого символа не

            // больше 0, тогда эта пара не

            // завершено.

            int i;

            for (i = 0; i < 26; i++)

                if (frequency[i] < 1)

                    break;

            if (i == 26)

                result++;

        }

    }

  

    return result;

}

  
// Код драйвера

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 реализация для поиска пар завершенных
// строки.

  

class GFG {

  

    // Возвращает количество полных пар из набора [0..n-1]

    // и set2 [0..m-1]

    static int countCompletePairs(String set1[], String set2[],

                                  int n, int m)

    {

        int result = 0;

  

        // Рассмотрим все пары обеих строк

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                // Создать конкатенацию текущей пары

                String concat = set1[i] + set2[j];

  

                // Вычисляем частоты всех символов

                // в объединенной строке.

                int frequency[] = new int[26];

                for (int k = 0; k < concat.length(); k++) {

                    frequency[concat.charAt(k) - 'a']++;

                }

  

                // Если частота любого символа не

                // больше 0, тогда эта пара не

                // завершено.

                int k;

                for (k = 0; k < 26; k++) {

                    if (frequency[k] < 1) {

                        break;

                    }

                }

                if (k == 26) {

                    result++;

                }

            }

        }

  

        return result;

    }

  

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен PrinciRaj19992

python3

# Python3 реализация для поиска пар
# полных строк.

  
# Возвращает количество полных пар
# из набора [0..n-1] и набора 2 [0..m-1]

def countCompletePairs(set1: list, set2: list

                              n: int, m: int) -> int:

    result = 0

  

    # Рассмотрим все пары обеих строк

    for i in range(n):

        for j in range(m):

  

            # Создать конкатенацию текущей пары

            concat = set1[i] + set2[j]

  

            # Вычислить частоты всех персонажей

            # в объединенной строке.

            frequency = [0] * 26

            for k in range(len(concat)):

                frequency[ord(concat[k]) - ord('a')] += 1

  

            # Если частота любого символа не

            # больше 0, то эта пара не

            # завершено.

            k = 0

            while k < 26:

                if frequency[k] < 1:

                    break

                k += 1

            if k == 26:

                result += 1

  

    return result

  
Код водителя

if __name__ == "__main__":

    set1 = ["abcdefgh", "geeksforgeeks"

            "lmnopqrst", "abc"]

    set2 = ["ijklmnopqrstuvwxyz"

            "abcdefghijklmnopqrstuvwxyz",

            "defghijklmnopqrstuvwxyz"]

  

    n = len(set1)

    m = len(set2)

  

    print(countCompletePairs(set1, set2, n, m))

  
# Этот код предоставлен
# sanjeev2552

C #

// C # реализация для поиска пар завершенных
// строки.

  

using System;

class GFG {

  

    // Возвращает количество полных пар из набора [0..n-1]

    // и set2 [0..m-1]

    static int countCompletePairs(string[] set1, string[] set2,

                                  int n, int m)

    {

        int result = 0;

  

        // Рассмотрим все пары обеих строк

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

                // Создать конкатенацию текущей пары

                string concat = set1[i] + set2[j];

  

                // Вычисляем частоты всех символов

                // в объединенной строке.

                int[] frequency = new int[26];

                for (int k = 0; k < concat.Length; k++) {

                    frequency[concat[k] - 'a']++;

                }

  

                // Если частота любого символа не

                // больше 0, тогда эта пара не

                // завершено.

                int l;

                for (l = 0; l < 26; l++) {

                    if (frequency[l] < 1) {

                        break;

                    }

                }

                if (l == 26) {

                    result++;

                }

            }

        }

  

        return result;

    }

  

    // Код драйвера

    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));

    }

}
// Эта статья предоставлена Ita_c.

Выход:

7

Метод 2 (Оптимизированный метод с использованием битовой манипуляции)
В этом методе мы сжимаем частотный массив в целое число. Мы назначаем каждый бит этого целого числа с символом, и мы устанавливаем его в 1, когда символ найден. Мы выполняем это для всех строк в обоих наборах. Наконец, мы просто сравниваем два целых числа в наборах, и если при объединении все биты установлены, они образуют полную пару строк.

C ++

// C ++ программа для поиска количества полных пар
#include <iostream>

using namespace std;

  
// Возвращает количество полных пар из набора [0..n-1]
// и set2 [0..m-1]

int countCompletePairs(string set1[], string set2[],

                       int n, int m)

{

    int result = 0;

  

    // con_s1 [i] будет хранить целое число,

    // установить биты, представляющие наличие / отсутствие символов

    // в строке set1 [i].

    // Аналогично con_s2 [i] собирается хранить целое число

    // чьи установленные биты представляют наличие / отсутствие

    // символы в строке set2 [i]

    int con_s1[n], con_s2[m];

  

    // Обрабатываем все строки в set1 []

    for (int i = 0; i < n; i++) {

        // инициализируем все биты в 0

        con_s1[i] = 0;

        for (int j = 0; j < set1[i].length(); j++) {

            // Установка ascii-кода char s [i] [j]

            // в 1 в сжатом целом числе.

            con_s1[i] = con_s1[i] | (1 << (set1[i][j] - 'a'));

        }

    }

  

    // Обрабатываем все строки в set2 []

    for (int i = 0; i < m; i++) {

        // инициализируем все биты в 0

        con_s2[i] = 0;

        for (int j = 0; j < set2[i].length(); j++) {

            // установка ascii-кода char s [i] [j]

            // в 1 в сжатом целом числе.

            con_s2[i] = con_s2[i] | (1 << (set2[i][j] - 'a'));

        }

    }

  

    // присваиваем переменную, у которой все 26 (0..25)

    // биты установлены в 1

    long long complete = (1 << 26) - 1;

  

    // Теперь рассмотрим каждую пару целых чисел в con_s1 []

    // и con_s2 [] и проверяем, завершена ли пара.

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < m; j++) {

            // если установлены все биты, строки

            // завершено!

            if ((con_s1[i] | con_s2[j]) == complete)

                result++;

        }

    }

  

    return result;

}

  
// Код драйвера

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 программа для поиска количества полных пар

class GFG {

  

    // Возвращает количество полных пар из набора [0..n-1]

    // и set2 [0..m-1]

    static int countCompletePairs(String set1[], String set2[],

                                  int n, int m)

    {

        int result = 0;

  

        // con_s1 [i] будет хранить целое число,

        // установить биты, представляющие наличие / отсутствие символов

        // в строке set1 [i].

        // Аналогично con_s2 [i] собирается хранить целое число

        // чьи установленные биты представляют наличие / отсутствие

        // символы в строке set2 [i]

        int[] con_s1 = new int[n];

        int[] con_s2 = new int[m];

  

        // Обрабатываем все строки в set1 []

        for (int i = 0; i < n; i++) {

  

            // инициализируем все биты в 0

            con_s1[i] = 0;

            for (int j = 0; j < set1[i].length(); j++) {

  

                // Установка ascii-кода char s [i] [j]

                // в 1 в сжатом целом числе.

                con_s1[i] = con_s1[i] | (1 << (set1[i].charAt(j) - 'a'));

            }

        }

  

        // Обрабатываем все строки в set2 []

        for (int i = 0; i < m; i++) {

  

            // инициализируем все биты в 0

            con_s2[i] = 0;

            for (int j = 0; j < set2[i].length(); j++) {

  

                // установка ascii-кода char s [i] [j]

                // в 1 в сжатом целом числе.

                con_s2[i] = con_s2[i] | (1 << (set2[i].charAt(j) - 'a'));

            }

        }

  

        // присваиваем переменную, у которой все 26 (0..25)

        // биты установлены в 1

        long complete = (1 << 26) - 1;

  

        // Теперь рассмотрим каждую пару целых чисел в con_s1 []

        // и con_s2 [] и проверяем, завершена ли пара.

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

  

                // если установлены все биты, строки

                // завершено!

                if ((con_s1[i] | con_s2[j]) == complete) {

                    result++;

                }

            }

        }

  

        return result;

    }

  

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен Rajput-Ji

C #

// C # программа для поиска количества полных пар

using System;

  

class GFG {

  

    // Возвращает количество полных пар из набора [0..n-1]

    // и set2 [0..m-1]

    static int countCompletePairs(String[] set1, String[] set2,

                                  int n, int m)

    {

        int result = 0;

  

        // con_s1 [i] будет хранить целое число,

        // установить биты, представляющие наличие / отсутствие символов

        // в строке set1 [i].

        // Аналогично con_s2 [i] собирается хранить целое число

        // чьи установленные биты представляют наличие / отсутствие

        // символы в строке set2 [i]

        int[] con_s1 = new int[n];

        int[] con_s2 = new int[m];

  

        // Обрабатываем все строки в set1 []

        for (int i = 0; i < n; i++) {

  

            // инициализируем все биты в 0

            con_s1[i] = 0;

            for (int j = 0; j < set1[i].Length; j++) {

  

                // Установка ascii-кода char s [i] [j]

                // в 1 в сжатом целом числе.

                con_s1[i] = con_s1[i] | (1 << (set1[i][j] - 'a'));

            }

        }

  

        // Обрабатываем все строки в set2 []

        for (int i = 0; i < m; i++) {

  

            // инициализируем все биты в 0

            con_s2[i] = 0;

            for (int j = 0; j < set2[i].Length; j++) {

  

                // установка ascii-кода char s [i] [j]

                // в 1 в сжатом целом числе.

                con_s2[i] = con_s2[i] | (1 << (set2[i][j] - 'a'));

            }

        }

  

        // присваиваем переменную, у которой все 26 (0..25)

        // биты установлены в 1

        long complete = (1 << 26) - 1;

  

        // Теперь рассмотрим каждую пару целых чисел в con_s1 []

        // и con_s2 [] и проверяем, завершена ли пара.

        for (int i = 0; i < n; i++) {

            for (int j = 0; j < m; j++) {

  

                // если установлены все биты, строки

                // завершено!

                if ((con_s1[i] | con_s2[j]) == complete) {

                    result++;

                }

            }

        }

  

        return result;

    }

  

    // Код драйвера

    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));

    }

}

  
// Этот код предоставлен 29AjayKumar

Выход:

7

Эта статья предоставлена Rishabh Jain . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Пары полных строк в двух наборах строк

0.00 (0%) 0 votes