計算透過交換給定數組中字串對的第一個字元而得到的新字串對的數量

在這個問題中，我們需要選擇一對字串並交換它們的第一個字元。之後，我們需要計算新對的總數。我們可以透過交換每對的第一個字元並檢查它是否存在於陣列中來解決這個問題。

解決這個問題的高效方法是使用哈希映射資料結構。

問題陳述 - 我們有一個包含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)

方法二

在這種方法中，我們將使用地圖資料結構來儲存地圖中的所有陣列值。之後，我們可以檢查地圖是否包含新產生的字串。如果沒有，我們可以將計數值增加 1。

演算法

• 定義變數‘cnt’

• 遍歷字串數組，並將所有數組值儲存在映射中。

• 使用兩個巢狀循環來取得陣列元素的所有配對。

• 取得字串對並將它們儲存在「first」和「second」變數中。

• 如果兩個字串的第一個字元不相等，則交換它們。

• 在地圖中，檢查是否包含新產生的字串。如果不是，請將「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)，因為我們使用映射來儲存所有陣列元素。

我們透過交換任何陣列元素的第一個字元來了解新產生的對的總數。我們對第二種方法的程式碼在時間複雜度上進行了最佳化，但第一種程式碼在空間複雜度上更好。

以上是計算透過交換給定數組中字串對的第一個字元而得到的新字串對的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！