【C++】1文字削除後に2つの文字列のいずれかと一致する文字列の数を求める方法

この記事では、2つの異なる文字列 s1 と s2 が与えられたときに、それらの一意な文字を組み合わせて文字列 S を作成し、S から1文字を削除した結果が s1 または s2 のいずれかと一致するパターンの数を求める方法を解説します。

例

例1

入力: S1 = "utter"、S2 = "butter"

出力: 1回の削除後に2つの文字列のいずれかと一致する文字列の数: 1

説明: 文字列 S として「butter」を作成します。S から文字「b」を削除すると「utter」になり、これは s1 と一致します。したがって、カウントは1です。

例2

入力: S1 = "fat"、S2 = "rat"

出力: 1回の削除後に2つの文字列のいずれかと一致する文字列の数: 2

説明: 文字列 S として「frat」を作成します。「r」を削除すると「fat」になり s1 と一致し、「f」を削除すると「rat」になり s2 と一致します。したがって、カウントは2です。

プログラムで使用しているアプローチ

• 2つの文字列 s1 と s2 を宣言し、文字列 s1 のサイズを計算して、以降の処理のために関数へ渡します。
• 変数 count を宣言し、答えとして考えられる最大値が2であるため、初期値を2に設定します。
• ループ走査用に、start と end という2つの一時変数を宣言します。
• 0から文字列 s1 のサイズまで FOR ループを実行し、ループ内で s1[i] が s2[i] と等しくない場合、start に i を代入して break します(最初の差分位置を検出)。
• 別の FOR ループを文字列 s1 のサイズ - 1 から 0 まで逆方向に実行し、ループ内で s1[i] が s2[i] と等しくない場合、end に i を代入して break します(最後の差分位置を検出)。
• end の値が start より小さい場合(両文字列が完全に一致している場合)、count を 26 × (文字列 s1 のサイズ + 1) に設定して返します。
• ELSE IF で start が end と等しい場合(差分が1文字だけの場合)、count をそのまま返します。
• それ以外の場合、i を start + 1 から end まで FOR ループで走査し、s1[i] が s2[i-1] と等しくなければ count を1減らして break します。
• 同様に、i を start + 1 から end まで FOR ループで走査し、s1[i-1] が s2[i] と等しくなければ count を1減らして break します。
• 最終的な count を返します。
• main 関数で結果を出力します。

コード例

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

int equal_removal(string S1, string S2, int size_S1) {
    int count = 2;
    int start;
    int end;

    for (int i = 0; i < size_S1; ++i) {
        if (S1[i] != S2[i]) {
            start = i;
            break;
        }
    }
    for (int i = size_S1 - 1; i >= 0; i--) {
        if (S1[i] != S2[i]) {
            end = i;
            break;
        }
    }
    if (end < start) {
        count = 26 * (size_S1 + 1);
        return count;
    } else if (start == end) {
        return count;
    } else {
        for (int i = start + 1; i <= end; i++) {
            if (S1[i] != S2[i - 1]) {
                count--;
                break;
            }
        }
        for (int i = start + 1; i <= end; i++) {
            if (S1[i - 1] != S2[i]) {
                count--;
                break;
            }
        }
        return count;
    }
}
int main() {
    string S1 = "utter";
    string S2 = "butter";
    int size_S1 = S1.length();
    cout << "Count of strings that become equal to one of the two strings after one removal are: " << equal_removal(S1, S2, size_S1);
    return 0;
}

上記のコードを実行すると、次の出力が生成されます。

出力

Count of strings that become equal to one of the two strings after one removal are: 1