小明最近在練習英文打字,每次練習後,系統會幫小明計算差異量。差異量計算方式為小明所打文字與正確文字相對位置不同英文字母的數目,例如 mouse 和 house 之間的差異量為 1。
他經常忘記英文字母在鍵盤的位置,所以常常打錯字。
系統提供一種「一對一」的校正功能,每次校正會將字串中所有一樣的指定字母都替換成另一個指定字母。一經校正,文字就無法再恢復,也就是第二次校正會以第一次校正後的結果為基礎來進行。
舉例來說,正確的單字為 ccdd,小明所打的文字為 aabb。若系統執行「a 替換成 c」的
校正,則 aabb 會校正為 ccbb。若系統緊接著執行「a 替換成 g」的校正,則不會有變化,因
為當前文字已經變成 ccbb 了,其中已不含 a。
請你寫一個程式計算小明所打的文字經校正後的差異量。
範例測資
範例輸入 | 範例輸出 |
---|---|
輸入第一列和第二列各有一個英文字串 S1 和 S2 (僅包含小寫英文字母,長度不超過 100,且 S1 和 S2 的長度保證相等),分別代表小明所打之文字以及正確文字,第三列有一個整數 N (1 ≤ N ≤100) 表示校正次數,接下來有 N 列,每列有兩個字元 Xi 和 Yi (1 ≤ i ≤ N),表示將當前文字中的 Xi 字元替代為 Yi。所謂當前文字是指從 S1 經過前面若干次校正後的文字。 | 輸出校正後兩個字串的距離 (經校正後的差異量)。 |
aabb ccdd 1 a c | 2 |
aabb ccdd 2 a b b c | 2 |
time game 2 i a t g | 0 |
elephant kangaroo 3 e o p k a n | 8 |
解題思路
使用 For迴圈 判斷目前字元是什麼,如果是 Xi 就將目前字元換成 Yi。
將字元替換完之後,在同一個位置比對不同的字串之字元是否一致,如果不一致答案就 +1。
範例程式碼-ZeroJudge K926: 錯字校正 (Correction)
#include <iostream>
using namespace std;
int main() {
cin.sync_with_stdio(0);
cin.tie(0);
string input, correct;
int N;
cin >> input >> correct >> N;
for (int i = 0; i<N; i++) {
char a, b;
cin >> a >> b;
for (int j = 0; j<input.length(); j++) {
if (input[j] == a) input[j] = b;
}
}
int ans = 0;
for (int i = 0; i<input.length(); i++) {
if (input[i] != correct[i]) ans++;
}
cout << ans << "\n";
}
//ZeroJudge K926
//Dr. SeanXD