计算通过交换给定数组中字符串对的第一个字符而得到的新字符串对的数量

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

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

问题陈述 - 我们有一个包含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 变量的值。

  

  Type Studio

  一个视频编辑器，提供自动转录、自动生成字幕、视频翻译等功能

  下载

• 如果数组中既没有第一个字符串，也没有第二个字符串，则将‘cnt’的值增加1。

• 返回‘cnt’变量的值。

示例

#include 
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)

方法二

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

算法

• 定义变量‘cnt’

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

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

• 获取字符串对并将它们存储在“first”和“second”变量中。

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

• 在地图中，检查是否包含新生成的字符串。如果不是，请将“cnt”的值增加 1。

• 返回‘cnt’值。

示例

#include 
#include 
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 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)，因为我们使用映射来存储所有数组元素。

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