C++で配列内に1文字だけ異なる文字列が存在するかどうかを確認する方法

文字列 s と、複数の文字列を格納した配列 A があるとします。このとき、配列の中に「元の文字列と長さが同じで、かつ1文字だけ異なる文字列」が存在するかどうかを判定する問題を考えてみましょう。

例えば、文字列が "banana" で、配列が ["bana", "orange", "banaba", "banapy"] の場合を想定します。このうち "banaba" は "banana" と長さが同じで、1文字だけ異なるため、結果は true となります。

解決のアプローチ

この問題は、以下の手順で解くことができます。

• 配列内の各文字列に対して、次の処理を繰り返します。
• まず、その文字列の長さが s と同じかどうかを確認します。長さが異なる場合はスキップします。
• 長さが同じ場合は、各文字を順に比較し、不一致がちょうど1箇所だけあるかどうかをチェックします。
• 1箇所だけの不一致が見つかれば true を返し、見つからなければ最終的に false を返します。

C++での実装例

#include<iostream>
#include<vector>
using namespace std;
bool hasOneCharMismatch(vector<string>arr, string s) {
    int n = arr.size();
    if (n == 0)
        return false;
    for (int i = 0; i < n; i++) {
        if (arr[i].size() != s.size())
            continue;
        bool difference = false;
        for (int j = 0; j < (int)arr[i].size(); j++) {
            if (arr[i][j] != s[j]) {
                if (!difference)
                    difference = true;
                else {
                    difference = false;
                    break;
                }
            }
        }
        if (difference)
            return true;
    }
    return false;
}
int main() {
    vector<string> arr;
    arr.push_back("bana");
    arr.push_back("orange");
    arr.push_back("banaba");
    arr.push_back("banapy");
    if(hasOneCharMismatch(arr, "banana")){
        cout << "One character mismatch found";
    }
    else{
        cout << "One character mismatch not found";
    }
}

実行結果

One character mismatch found

コードのポイント

このアルゴリズムでは、変数 difference をフラグとして使用しています。最初に不一致文字が見つかった時点でフラグを立て、2つ目の不一致が見つかった時点で即座にループを抜けて次の文字列へ進みます。これにより、無駄な比較を避け、効率的に判定を行うことができます。

計算量は、配列の要素数を n、文字列の長さを m とすると、最悪の場合 O(n × m) となります。長さが異なる文字列は早期にスキップされるため、実際の処理はより高速に動作するケースが多いです。