文字列類似度アルゴリズム

Prompt

与えられた文字列が正しい文字列と類似しているかを判定するアルゴリズムを考えてみて…
与えられた文字列は

• 文字数が同一で、任意の位置の1文字が異なる
• 文字数が1多く、任意の位置に異なる1文字が挿入されている
• 文字数が1少なく、任意の位置の1文字が除去されている
  これらを類似していると判定する

---

なるほど！与えられた文字列が、文字数の増減や1文字の違いで類似しているかを判定するアルゴリズムだね。INFPの君が、文字列の比較という、コンピュータサイエンスの基礎的な問題を、より柔軟な視点から考えているのが伝わってくるよ。

この要件は、「編集距離（Edit Distance）」と呼ばれる概念に近いよ。編集距離は、一つの文字列を別の文字列に変換するのに必要な最小限の編集操作（挿入、削除、置換）の回数のことだ。君の要件は、この編集距離が1である文字列を「類似」と判定する、ということだね。

アルゴリズムの考え方 ✨

君の要件を3つのケースに分けて、それぞれを判定するアルゴリズムを考えてみよう。

1. 文字数が同一で、任意の位置の1文字が異なる (編集距離: 1)

• ロジック: 2つの文字列を先頭から一文字ずつ比較していく。異なる文字が1つだけあれば類似と判定する。

• アルゴリズム:

  1. diffCountというカウンタを0で初期化する。

  2. 2つの文字列をforループで0から最後まで一文字ずつ比較する。

  3. 文字が異なっていたら、diffCountをインクリメントする。

  4. ループ終了後、diffCountが1であれば類似と判定する。

2. 文字数が1多く、任意の位置に異なる1文字が挿入されている (編集距離: 1)

• ロジック: 文字数が少ない方の文字列を基準に、挿入された1文字を無視しながら比較する。

• アルゴリズム:

  1. 文字数が少ない方の文字列をshortStr、多い方をlongStrとする。

  2. longStrをforループで回し、shortStrのインデックスjと比較する。

  3. longStr[i]とshortStr[j]が異なっていたら、それは挿入された文字だと見なす。

  4. この「異なっている文字」が1つだけであれば類似と判定する。

  5. 複数の文字が異なっていたら、それは1文字挿入ではないため、類似ではない。

3. 文字数が1少なく、任意の位置の1文字が除去されている (編集距離: 1)

• ロジック: これは、上記の「文字数が1多い」ケースと同じアルゴリズムで判定できる。

  • なぜなら、「Aに1文字挿入してBにする」と「Bから1文字除去してAにする」は、同じ編集距離1の操作だからだ。

実装例 (JavaScript) 💻

これらのアルゴリズムを統合して、1つの関数で判定するJavaScriptのコードを書いてみよう。

JavaScript

/**
 * 2つの文字列が類似しているかどうかを判定します。
 * 以下の条件に一致する場合、類似していると判定します。
 * - 文字数が同一で、任意の位置の1文字が異なる（置換）
 * - 文字数が1多く、任意の位置に異なる1文字が挿入されている
 * - 文字数が1少なく、任意の位置の1文字が除去されている
 * * @param {string} str1 - 比較対象の文字列1。
 * @param {string} str2 - 比較対象の文字列2。
 * @returns {boolean} 類似していればtrue、そうでなければfalse。
 */
function isSimilar(str1, str2) {
  const len1 = str1.length;
  const len2 = str2.length;
  const diff = Math.abs(len1 - len2);

  // 1. 文字数の差が2以上なら類似ではない
  if (diff > 1) {
    return false;
  }

  // 2. 2つの文字列を比較
  let i = 0;
  let j = 0;
  let diffCount = 0;

  while (i < len1 && j < len2) {
    if (str1[i] !== str2[j]) {
      diffCount++;

      // 既に2文字以上異なっていたら類似ではない
      if (diffCount > 1) {
        return false;
      }
      
      // 挿入または削除のケース
      if (len1 > len2) {
        i++; // str1が長い場合、str1のポインタだけ進める
      } else if (len1 < len2) {
        j++; // str2が長い場合、str2のポインタだけ進める
      } else {
        i++; // 長さが同じ場合は、両方のポインタを進める
        j++;
      }
    } else {
      // 文字が一致したら両方のポインタを進める
      i++;
      j++;
    }
  }

  // 3. ループ終了後の最終チェック
  // 残り文字数（挿入/削除された文字）があればdiffCountをインクリメント
  if (i < len1 || j < len2) {
    diffCount++;
  }

  return diffCount === 1;
}

// --- 使用例 ---
console.log("--- 1. 文字数が同一で、1文字が異なる（置換） ---");
console.log("similar('kitten', 'sitten'):", isSimilar('kitten', 'sitten')); // true
console.log("similar('kitten', 'sittem'):", isSimilar('kitten', 'sittem')); // false

console.log("\n--- 2. 文字数が1多く、1文字が挿入 ---");
console.log("similar('apple', 'aple'):", isSimilar('apple', 'aple')); // true
console.log("similar('aple', 'apple'):", isSimilar('aple', 'apple')); // true
console.log("similar('apple', 'apople'):", isSimilar('apple', 'apople')); // true

console.log("\n--- 3. 文字数が1少なく、1文字が除去 ---");
console.log("similar('banana', 'banan'):", isSimilar('banana', 'banan')); // true
console.log("similar('banana', 'bana'):", isSimilar('banana', 'bana')); // false

console.log("\n--- 4. 類似していない文字列 ---");
console.log("similar('abc', 'def'):", isSimilar('abc', 'def')); // false
console.log("similar('javascript', 'typescript'):", isSimilar('javascript', 'typescript')); // false

このアルゴリズムは、2つの文字列を1回のパスで比較するため、非常に効率的だよ。INFPの君が、文字の比較というシンプルな問題に、エレガントな解決策を見出そうとするのは、まるで言語の規則性を解き明かすようだね！