計算在僅一個位置上不同的字串對的數量

簡介

字串由字母數字字元組成，每個字元都與一個確定的位置相關聯。字元的位置範圍從 0 到字串長度。在一個位置完全不同的字元稱為相鄰字元。

在本文中，我們將開發一種程式碼，該程式碼將一個字串陣列作為輸入，這些字串在一個位置上完全不同。讓我們看下面的例子來更好地理解這個主題 -

範例

範例 1 - str - {“abc”、“cba”、“dbc”、“acc”}

輸出 - 2

例如，在下面的範例中，可以產生兩對{“abc”，“dbc”}和{“abc”，acc”}。這些字串分別僅在一個字元位置上有所不同。

在本文中，我們將開發一個程式碼，利用映射來儲存相似的字串以及取得字串對總數的模式。 C 映射利用鍵值對以便以恆定的時間複雜度儲存和檢索資料。

文法

substr()

substr() 方法用於存取較大字串中從 start 到 end-1 位置的子字串。所有要存取的索引應該是連續且有序的。

參數 -

st - 起始位置

end - 終止子字串存取的結束位置

演算法

• 接受字串向量，字串

• #最初維護一個計數器來儲存滿足條件的總對的計數。

• 維護兩個映射來儲存相同的字串以及滿足保留通配符的模式的字串。讓我們假設這個映射是 m1。

• 維護另一個映射來儲存相似的字串。讓我們假設這個映射是 m2。

• 對輸入數組執行迭代。

• 每次觀察到類似類型的字串，m2 映射中其對應的計數就會遞增

• #子字串是透過使用通配符替換字串的各個字元來建立的

• 每次觀察到類似類型的模式，m1 圖中對應的計數就會增加

• 計算分別在 m1 和 m2 中觀察到的字串對的總和。

• 使用這些總和值來增加計數。

範例

以下 C 程式碼片段用於將字串陣列作為輸入，並計算僅在一個位置不同的對的總數 -

//including the required libraries
#include <bits/stdc++.h>
using namespace std;
 
// Function to return the count of same pairs
int countPairs(map<string, int> &d) {
   //maintaining the count 
   int sum = 0;
   for (auto i : d)
       sum += (i.second * (i.second - 1)) / 2;
 
   return sum;
}
//called method to calculate strings differing by one character
void chardiff(vector<string> &array, int len , int n ) {
   //count to store pairs
    int cnt = 0;
   //storing strings with wildcard characters
    map<string, int> pattern;
   //storing equivalent strings
    map<string, int> similar;
   //iterating over the array
   for (auto str : array) {
      //if two strings are same , increment the count
       similar[str]+= 1;
 
      // Iterating on a single string
       for (int i = 0; i < len ; i++) {
      // Adding special symbol to the string
       string first = str.substr(0, i);
       string second = str.substr(i + 1);
       string temp =  first + "//" + second ;
 
      //incrementing if similar pattern 
        pattern[temp]+=1;
      }
   }
 
   // Return counted pairs - equal pairs
   int chnged = countPairs(pattern);
   int sim = countPairs(similar);
   cnt =  chnged - sim * len;
   cout << "The count of pairs satisfying the condition are : " << cnt; 
}
 
//calling the main method
int main() {
   int n = 4, len = 3;
   //getting a vector of strings to process
   vector<string> strings = {"get","set","bet","bat"};
   cout << "Vector of strings : " << "\n" ;
   for(auto s : strings){
       cout << s <<"\n";
   }
   //one character different
   chardiff(strings, len , n );
 
   return 0;
}

輸出

Vector of strings − 
get
set
bet
bat
The count of pairs satisfying the condition are − 4

結論

Maps 以 O(1) 時間複雜度模擬記錄插入和更新的過程。 C 中的 substring 方法可用於以指定索引之間的順序存取字串的字元。 n 和 n-1 的積除以 2 即可得到任意數量的對的總和。

以上是計算在僅一個位置上不同的字串對的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！