字串由字母數字字元組成,每個字元都與一個確定的位置相關聯。字元的位置範圍從 0 到字串長度。在一個位置完全不同的字元稱為相鄰字元。
在本文中,我們將開發一種程式碼,該程式碼將一個字串陣列作為輸入,這些字串在一個位置上完全不同。讓我們看下面的例子來更好地理解這個主題 -
範例 1 - str - {“abc”、“cba”、“dbc”、“acc”}
輸出 - 2
例如,在下面的範例中,可以產生兩對{“abc”,“dbc”}和{“abc”,acc”}。這些字串分別僅在一個字元位置上有所不同。
在本文中,我們將開發一個程式碼,利用映射來儲存相似的字串以及取得字串對總數的模式。 C 映射利用鍵值對以便以恆定的時間複雜度儲存和檢索資料。
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中文網其他相關文章!