【C++】追加と削除の操作だけで文字列を別の文字列に変換できるか判定する方法

このチュートリアルでは、「末尾に文字を追加する」操作と「末尾の文字を削除する」操作のみを使って、ある文字列を別の文字列に変換できるかどうかを判定するプログラムを、C++で実装する方法を解説します。

問題の概要

2つの文字列 str1 と str2、および整数 k が与えられます。求めたいのは、ちょうど k 回の追加・削除操作を組み合わせることで、str1 を str2 に変換できるかどうかです。

判定のポイント

• 合計長が k 未満の場合： 2つの文字列の長さの合計が k より小さければ、余った操作を「1文字削除してすぐ追加し直す」という無駄打ちで消費できるため、必ず変換可能です。
• 共通プレフィックスの活用： まず、両文字列の先頭から一致している文字数（共通長）を求めます。この部分は変更する必要がありません。
• 偶奇のチェック： 共通部分を残す場合に必要な最小操作回数は「len1 − 共通長 ＋ len2 − 共通長」です。余分な操作は削除と追加のペアで2回ずつ増えるため、(k − len1 − len2 ＋ 2×共通長) が偶数になれば、ちょうど k 回で変換できます。

C++での実装例

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

// 2つの文字列間の変換が可能かどうかを判定する関数
bool if_convert(string str1, string str2, int k){
    // 合計の長さがk未満なら、余分な操作で調整できるため必ず変換可能
    if ((str1.length() + str2.length()) < k)
        return true;
    // 両文字列に共通する先頭部分の長さを求める
    int commonLength = 0;
    for (int i = 0; i < min(str1.length(), str2.length()); i++) {
        if (str1[i] == str2[i])
            commonLength++;
        else
            break;
    }
    // 操作回数の偶奇が一致すれば、ちょうどk回で変換可能
    if ((k - str1.length() - str2.length() + 2 * commonLength) % 2 == 0)
        return true;
    return false;
}

int main(){
    string str1 = "tutorials", str2 = "point";
    int k = 5;
    if (if_convert(str1, str2, k))
        cout << "Yes";
    else
        cout << "No";
    return 0;
}

実行結果

No

コードの解説

この例では、"tutorials"（9文字）を "point"（5文字）に変換しようとしています。先頭文字が一致しないため共通長は0となり、必要な最小操作回数は 9 ＋ 5 ＝ 14 回です。しかし k ＝ 5 では操作回数が足りず、偶奇の条件も満たさないため、出力は「No」になります。

このように、共通プレフィックスの長さと操作回数の偶奇を確認するだけで、効率よく判定できるのがこのアルゴリズムの魅力です。計算量は O(min(len1, len2)) と非常に軽量です。