資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學精確相差一位的字串對計數
引言
字串由字母數字字元組成，每個字元都與一個確定的位置相關聯。字元的位置範圍從 0 到字串長度。在恰好一個位置上不同的字元被稱為相鄰字元。
在本文中，我們將開發一段程式碼，該程式碼將輸入一個字串陣列，這些字串在恰好一個位置上有所不同。讓我們來看下面的例子，以便更好地理解這個主題：
示例
示例 1 − str − {“abc”, “cba”, “dbc” , “acc”}
輸出 − 2
例如，在下面的例子中，可以生成兩對 {“abc”,”dbc”} 和 {“abc”, “acc”}。這些字串分別只有一個字元位置不同。
在本文中，我們將開發一個使用 map 來儲存相似字串以及模式以獲取字串對總數的程式碼。C++ map 使用鍵值對以恆定時間複雜度儲存和檢索資料。
語法
substr()
substr() 方法用於從起始位置到結束位置-1訪問更大字串的子字串。所有要訪問的索引都應該是連續且有序的。
引數：
st − 起始位置
end − 結束位置，用於終止子字串的訪問
演算法
接受一個字串向量 strings
最初，維護一個計數器來儲存滿足條件的總對數。
維護兩個 map 來儲存相同的字串以及滿足模式（保留萬用字元字元）的字串。讓我們假設這個 map 為 m1。
另一個 map 用於儲存相似的字串。讓我們假設這個 map 為 m2。
對輸入陣列進行迭代。
每次觀察到相同型別的字串時，其對應的計數在 m2 map 中遞增。
使用字串的相應字元替換萬用字元字元來建立子字串。
每次觀察到相同型別的模式時，其對應的計數在 m1 map 中遞增。
計算分別在 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
結論
map 模擬了在 O(1) 時間複雜度下插入和更新記錄的過程。C++ 中的 substr 方法可以用於按順序訪問指定索引之間字串的字元。直到任何數字 n 的對的總和由 n 和 n-1 的乘積除以 2 得到。
249 次瀏覽
