２つの文字列は１回の変換で等しくなるか

問題

２つの文字列が与えられた際に、１回の変換(文字の追加、削除、置き換え）で等しくなるか

考え方

文字列の長さが等しい時は１文字だけ違ったら、置き換えで対応できます。 str1[i] != str2[i]となる数を判定して、これが１以下ならture。

文字列の長さが異なる時は、まず、１文字の差だけか確認します。 少ない方の文字列(M)が長い方の文字列(N)の中に順番通りに入っているか確認します。 どうするのが効率がいいかわからないですが、i:0->N-1として、少ない方の文字列のindexjをstr1[j] == str2[i]の時にインクリメントして最後にj == Mならtrueとします。

どれにも適さないなら、falseを返します。

計算量

時間計算量はO(N)ですみます。

コード例

#include<iostream>

using namespace std;

bool add(string str1, string str2){
    // str1.length > str2.length()で入れる
    int i, j;
    j = 0;
    if(str1.length() < str2.length()){
        cout << "使い方が違います!" << endl;
    }else{
        for(i=0; i<str1.length(); i++){
            if(str1.substr(i, 1)==str2.substr(j, 1)){
                j++;
            }
        }
        if(j==str2.length()){
            return true;
        }
    }
    return false;
}

bool check(string str1, string str2){
    int  i, j, n, m;
    string s;
    n = str1.length();
    m = str2.length();
    // N < M
    j = 0;
    if(n-1 == m){
        return add(str1, str2);
    }else if(n == m-1){
        return add(str2, str1);
    }else if(n==m){
        for(i=0; i<m; i++){
            if(str1.substr(i, 1)!=str2.substr(i, 1)){
                j++;
            }
        }
        if(j<=1){
            return true;
        }
    }
    return false;
}

int main(void){
    bool flg;
    string str1 = "apple";
    string str2 = "abnple";
    flg = check(str1, str2);
    cout << "一回の変換で良いか? " << boolalpha << flg << endl;

    return 0;
}

参考

問題は 世界で闘うプログラミング力を鍛える本 | マイナビブックス から。