3番目の文字列との交換で2つの文字列を一致させられるかを判定するC++プログラム

同じ長さ n の3つの文字列 S・T・U が与えられているとします。0 から n-1 までの各インデックス i に対して、U[i] を S[i] または T[i] のどちらか一方と交換する必要があります。つまり、合計でちょうど n 回の交換操作を行うことになります。この一連の操作を終えたとき、文字列 S を T と完全に一致させられるかどうかを判定するのが本問題です。

考え方

実は、この問題は各インデックスごとに独立して考えることができます。インデックス i の交換は S[i] と T[i] のどちらか一方にしか影響しないためです。

• U[i] を S[i] と交換した場合：S[i] は元の U[i] の文字になり、T[i] は変化しません。よって S[i] == T[i] となるのは U[i] == T[i] のときです。
• U[i] を T[i] と交換した場合：T[i] は元の U[i] の文字になり、S[i] は変化しません。よって S[i] == T[i] となるのは S[i] == U[i] のときです。

したがって、すべての i について「S[i] が U[i] と等しい」または「T[i] が U[i] と等しい」の少なくとも一方が成り立てば答えは Yes、どちらにも一致しない位置が1つでも存在すれば答えは No となります。

解くための手順

以下の手順に従って判定します。

for initialize i := 0, when S[i] is non-zero, update (increase i by 1), do:
    if S[i] is not equal to U[i] and T[i] is not equal to U[i], then:
        return false
    return true

C++による実装例

理解を深めるために、実際の実装を見てみましょう。

#include <bits/stdc++.h>
using namespace std;

bool solve(string S, string T, string U) {
    for (int i = 0; S[i]; ++i)
        if (S[i] != U[i] && T[i] != U[i])
            return false;
    return true;
}
int main() {
    string S = "abc";
    string T = "bca";
    string U = "bca";
    cout << solve(S, T, U) << endl;
}

入力

"abc", "bca", "bca"

出力

1

出力が 1（true）となり、条件を満たすことが確認できました。この例では、すべての i について U[i] を S[i] と交換すれば S は "bca" になり、T は最初から "bca" であるため一致します。計算量は文字列の長さを n とすると O(n) で、非常に効率的なアルゴリズムです。