Программа Python3 для проверки, может ли данная строка быть образована двумя другими строками или их перестановками

Учитывая строку str и массив строк arr[] , задача состоит в том, чтобы проверить, может ли данная строка быть образована любой парой строк из массива или их перестановками. Примеры:

Input: str = “amazon”, arr[] = {“loa”, “azo”, “ft”, “amn”, “lka”} Output: Yes The chosen strings are “amn” and “azo” which can be rearranged as “amazon”. Input: str = “geeksforgeeks”, arr[] = {“geeks”, “geek”, “for”} Output: No

Метод 1. В этом подходе мы начинаем с сортировки заданной строки, затем запускаем два вложенных цикла, чтобы одновременно выбрать две строки из заданного массива и объединить их. Затем мы сортируем результирующую строку, которую мы получили после конкатенации.
Затем мы сравниваем эту строку с заданной строкой и проверяем, равны они или нет. Если найдены равные, мы возвращаем true.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(nlogn+m ² klogk), где n — размер заданной строки, m — размер данного массива, а k — максимальный размер, полученный путем сложения любых двух строк (который в основном является суммой размер двух самых длинных строк в данном массиве).

Метод 2. Сортировка подсчетом может использоваться для сокращения времени выполнения описанного выше подхода. Сортировка подсчетом использует таблицу для хранения количества каждого символа. У нас есть 26 алфавитов, поэтому мы создаем массив размером 26 для хранения количества каждого символа в строке. Затем возьмите символы в порядке возрастания, чтобы получить отсортированную строку. Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(n+m ² k), где n — размер заданной строки, m — размер заданного массива, а k — максимальный размер, полученный путем сложения любых двух строк (что в основном является суммой размер двух самых длинных строк в данном массиве).

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