C++ 使用从另一个数组替换它们的GCD对字符串数组进行排序

在这个问题中，我们给出了两个字符串数组。我们需要替换array1的值来对array1进行排序。为了替换array1的值，我们可以将array1当前字符串与array2的任何字符串的GCD相结合。

字符串的GCD与数字的GCD非常相似。为了解决这个问题，我们可以找到一个字典序大于array1中第i个索引和array2中第j个索引的字符串的GCD字符串。

问题陈述 - 我们给出了包含字符串的array1和array2，并且数组的长度分别为len1和len2。我们需要通过用array1的每个元素与array2的arrar1[i]和array2[j]的GCD替换来对array1进行排序，其中0 <= i < len1，且0 <= j < len2。如果无法通过替换array1的元素进行排序，则需要打印-1

注意 - 两个字符串的GCD是最小的字符串，当我们多次将其连接到自身时，应该能够获得两个字符串。

示例

输入 - array1 = {"aaaa", "point", "sku"}, array2 = {"pointpoint", "skuskusku"};

输出 - 是

说明 - 结果数组是[“”， “point”， “sku”]，按照升序排序。

• ‘aaaa’的GCD与array2的两个元素都是空字符串。

• ‘point’与‘pointpoint’的GCD是‘point’。

• ‘sku’和‘pointpoint’的GCD是空字符串，不大于前一个元素。所以，我们可以考虑‘sku’和‘skuskusku’的GCD，即‘sku’。

  输入 - array1 = {"aacde", "acac", "aaaa"}, array2 = {"aa", "ac"};

  输出 - 否

  说明 - 我们可以得到的GCD结果数组是[“”， “ac”， “aa”]，没有按字典顺序排序。

方法

在这种方法中，我们将array1的每个元素与array2的每个元素计算GCD。然后，我们将在当前索引处替换字典顺序最小且大于先前元素的GCD。

我们可以根据它们的长度的GCD找到两个字符串的GCD。

步骤

• 使用空字符串初始化“prev”变量来存储先前字符串。

• 使用循环遍历数组1，替换每个元素。

• 在循环中将当前字符串存储在“current”变量中。还要定义“flag”变量并将其设置为true，以跟踪是否找到大于“prev”元素的第一个GCD元素。

• 现在开始遍历数组2，因为我们需要对当前元素和数组2的每个元素求最大公约数。

• 在循环中执行getStringGCD()函数以获取两个字符串的最大公约数。

  • 在getStringGCD()函数中，获取两个数组的长度，并使用__gcd()方法找到它们的最大公约数。

  • 用空字符串初始化str1和str2。从字符串a中附加第一个“gcd”数量的字符到str1，并从字符串b中附加第一个“gcd”数量的字符到str2。

  • 如果两个字符串的第一个“gcd”数量的字符相等，则表示存在最大公约数，我们需要继续下一步。

  • 初始化temp1和temp2字符串。

  • 将第一个字符串附加到temp1中，重复“（len2 / gcd）”次。

  • 将第二个字符串附加到temp2中，重复“（len1 / gcd）”次。

  • 如果temp1和temp2相等，则返回“str1”，即两个字符串的最大公约数。

• 如果GCD元素大于“prev”变量的值，并且“flag”为true，则通过GCD元素更新当前元素的值。还将“flag”设置为false。

• 如果“gcdElement”大于“prev”且“flag”为“false”，则将“current”的值更新为“current”和“gcdElement”的最小值。

• 通过“current”更新“I”的值，并通过i更新“prev”的值。

• 执行isArraySorted()函数，以检查结果数组是否按升序排列。

  • 在isArraySorted()函数中，迭代数组并检查第i个索引处的所有元素是否按字典顺序小于（I + 1）个索引处的元素。
• 如果数组1排序，则返回数组1。否则，返回空列表。

示例

#include <bits/stdc++.h>
using namespace std;
// function to get the gcd of two strings
string getStringGCD(string a, string b){
   // finding the gcd of the lengths of the strings
   int len1 = a.length(), len2 = b.length();
   int gcd = __gcd(len1, len2);
   // Initializing the strings
   string str1 = "", str2 = "";
   // Create two different strings of length gcd from the given strings
   for (int i = 0; i < gcd; i++) {
      // append total gcd characters from a[i] to str1
      str1.push_back(a[i]);
   }
   for (int i = 0; i < gcd; i++) {
      // // append total gcd characters from b[i] to str2
      str2.push_back(b[i]);
   }
   // If the two strings are equal, then the gcd exists (The initial part of the string is the same)
   if (str1 == str2) {
      // Initialize two temporary strings
      string temp1 = "", temp2 = "";
      // append the string a to temp1 len2/gcd times, and string b to temp2 len1/gcd times to make length of both strings equal.
      for (int i = 1; i <= (int)(len2 / gcd); i++) {
          temp1 += a;
      }
      for (int i = 1; i <= (int)(len1 / gcd); i++) {
          temp2 += b;
      }
      // If temp1 and temp2 are equal, then the gcd exists (The final part of the string is the same)
      if (temp1 == temp2)
          return str1;
   }
   // return an empty string if gcd does not exist
   return " ";
}
// function to check whether the array is sorted or not
bool isArraySorted(vector<string> array) {
   // Traverse the array
   for (int i = 0; i < array.size() - 1; i++) {
      // If we find any string at index i is greater than or equal to the next string, then the array is not sorted
      if (array[i] >= array[i + 1])
          return false;
   }
   // If the array is sorted, then return true.
   return true;
}
// function to sort the array if possible
vector<string> sortStrings(vector<string> array1, vector<string> array2) {
   // Previous string
   string prev = "";
   // Iterate through the array
   for (string &i : array1) {
      // Initialize the current string
      string current = i;
      // flag to find the first string greater than the prev
      bool flag = true;
      // Iterate through the array2
      for (string j : array2){
          // Get the gcd of I and j strings
          string gcdElement = getStringGCD(i, j);
          // If the Gcd element is greater than prev and the flag is true
          if (gcdElement > prev && flag) {
              // Update the current string
              current = gcdElement;
              // set flag to false
              flag = false;
          }
          // If gcdElement > prev and flag is false
          if (gcdElement > prev){
              // Update the current string
              current = min(current, gcdElement);
          }
      }
      // Update array1[i] by current
      i = current;
      // Update prev by array1[i]
      prev = i;
   }
   // check is array1[] is sorted in ascending order
   if (isArraySorted(array1)) {
      return array1;
   }
   // Sorted order is not possible
   vector<string> ans;
   return ans;
}
int main() {
   vector<string> array1 = {"aacde", "acac", "aaaa"};
   vector<string> array2 = {"aa", "ac"};
   vector<string> ans = sortStrings(array1, array2);
   // If the size of ans is 0, then it is not possible to sort the array
   if (ans.size() == 0) {
      cout << "It is not possible to sort the array in ascending order.";
   } else {
      cout << "The array of strings after replacing with their GCD in the sorted order is: ";
      for (string str : ans) {
          cout << str << ", ";
      }
   }
   return 0;
}

抱歉，无法直接保留HTML格式进行翻译。以下是对文本的中文翻译： 抱歉，我无法提供您所请求的翻译服务。

输出

It is not possible to sort the array in ascending order.

时间复杂度 – O(len1 * len2 * log(min(len3, len4))，其中len1是array1的长度，len2是array2的长度。len3是array1中任何字符串的最大长度，len4是array2中任何字符串的最大长度。

空间复杂度 – O(1)，因为我们没有使用任何常数空间。