C++ 计算通过交换给定数组中字符串对的第一个字符可以获得的新字符串对的数量

在这个问题中，我们需要选择一对字符串并交换它们的第一个字符。之后，我们需要计算所有新字符串对的总数。我们可以通过交换每对的第一个字符并检查它是否存在于数组中来解决这个问题。

解决这个问题的高效方法是使用哈希映射数据结构。

问题陈述 - 我们有一个包含N个字符串的数组。我们可以从数组的所有元素中选择任意两个字符串，并交换两个字符串的第一个字符。我们需要计算不在数组中的新生成字符串对的总数。

示例

输入 - array[] = {“should”, “would”, “can”};

输出 - 3

解释 - 新生成的字符串对可以是could和wan。另一对可以是whould和sould。第三对可以是san和chould。

输入 - array[] = {“demo”, “test”};

输出 - 1

解释 - 新生成的不在数组中的字符串对是temo和dest。

方法1

在这种方法中，我们将使用两个嵌套循环来获取数组元素的所有字符串对。然后，我们将交换这两个对的第一个字符。接下来，我们将使用第三个嵌套循环来检查数组是否包含该对。

步骤

• 定义‘cnt’变量并初始化为0，用于存储字符串对的总数。

• 使用两个嵌套循环遍历字符串数组，并获取每对数组元素。

• 获取当前对的两个字符串。

• 如果两个字符串的第一个字符不相等，则交换它们。

• 定义‘isFirst’和‘isSecond’变量，并初始化为false，以跟踪新生成的字符串是否存在于数组中。

• 使用第三个嵌套循环来检查新生成的字符串是否在数组中。根据数组中的字符串更新isFirst和isSecond变量的值。

• 如果两个字符串都不在数组中，则将‘cnt’的值增加1。

• 返回‘cnt’变量的值。

示例

#include <iostream>
using namespace std;
// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
   // Stores the count of pairs
   int cnt = 0;
   // Get all the pairs of strings
   for (int i = 0; i < len; i++){
      for (int j = i + 1; j < len; j++){
         // store single pair of strings
         string first = array[i], second = array[j];
         // If both strings' first characters are not equal, swap them.
         if (first[0] != second[0]){
            swap(first[0], second[0]);
            bool isFirst = false;
            bool isSecond = false;
            // Check whether the strings are present in the array or not
            for (int k = 0; k < len; k++){
               if (array[k] == first){
                  isFirst = true;
               }
                  if (array[k] == second){
                     isSecond = true;
                  }
              }
               // If both the strings are present in the array, then increment the cnt by 1
                if (isFirst == false && isSecond == false){
                    cnt++;
              }
          }
       }
    }
    return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

输出

Total number of new pairs we can generate by swapping the first characters of given strings is 3

时间复杂度 - O(N^3)，因为使用了三个嵌套循环。

空间复杂度 - O(1)

方法2

在这种方法中，我们将使用map数据结构将所有的数组值存储在map中。然后，我们可以检查map是否包含新生成的字符串。如果不包含，我们可以将计数值增加1。

步骤

• 定义变量‘cnt’。

• 遍历字符串数组，并将所有数组值存储在map中。

• 使用两个嵌套循环获取数组元素的所有组合。

• 获取字符串组合，并将它们存储在变量‘first’和‘second’中。

• 如果两个字符串的首字符不相等，则交换它们。

• 在map中检查是否包含新生成的字符串。如果不包含，则将‘cnt’的值增加1。

• 返回‘cnt’的值。

示例

#include <iostream>
#include <unordered_map>
using namespace std;

// function to find the count of pairs of strings that can be formed by swapping the first character of the strings
int newStringPairs(string array[], int len){
    // to store the total number of new pairs
    int cnt = 0;
    // add all strings to the array map
    unordered_map<string, int> str_map;
    for (int i = 0; i < len; i++){
       str_map[array[i]]++;
    }
    //find all pairs of strings that can be formed by swapping the first character of the strings
    for (int i = 0; i < len; i++){
       for (int j = i + 1; j < len; j++){
          // get the current pair of strings
          string first = array[i];
          string second = array[j];
          // If the first character of both strings is not the same, then swap them
          if (first[0] != second[0]){
             swap(first[0], second[0]);
             // If both strings are not present in the map, then the increment count
             if (str_map[first] == 0 && str_map[second] == 0){
                cnt++;
               }
            }
         }
      }
   return cnt;
}
int main(){
   string array[] = {"should", "would", "can"};
   int N = sizeof(array) / sizeof(array[0]);
   cout << "Total number of new pairs we can generate by swapping the first characters of given strings is " << newStringPairs(array, N);
   return 0;
}

输出

Total number of new pairs we can generate by swapping the first characters of given strings is 3

时间复杂度 - O(N^2)，因为我们使用了两个嵌套循环。

空间复杂度 - O(N)，因为我们使用map来存储所有数组元素。

我们通过交换任意数组元素的第一个字符来得到新生成的配对的总数。我们在第二种方法中优化了时间复杂度，但是第一个代码在空间复杂度上更好。