【JavaScript】文字の並べ替えなしで、一方の文字列から一部の文字を削除してもう一方の文字列を形成できるか判定する方法

課題

JavaScriptで、2つの文字列(str1 と str2)を引数として受け取る関数を実装します。この関数は、str1から一部の文字を削除することでstr2を形成できるかどうかを判定します。ただし、文字の並び順を一切変えてはいけないという条件が付きます。

言い換えれば、これは「str2 が str1 の部分列(サブシーケンス)であるか」を調べる問題です。使用する文字の種類や数が揃っているだけでは不十分で、出現順序まで一致している必要がある点がポイントです。

入力例

const str1 = 'sjkfampeflef';
const str2 = 'sample';

この場合、'sample' の各文字が 'sjkfampeflef' の中に左から順に見つかるため、結果は true となります。

解決アプローチ:ツーポインタ法

並び順を保ったまま効率よく判定するには、2つのインデックス(ポインタ)を使った線形走査が有効です。

1. str1 を先頭から走査するポインタ j と、str2 側の現在位置を示すポインタ i を用意する。
2. str1[j] と str2[i] が一致したら i を1つ進める。
3. 走査終了時に i が str2.length に達していれば、str2 の全文字を順序どおりに見つけられたことになるので true を返す。

この方法なら計算量は O(n)(n は str1 の長さ)に抑えられ、配列への分割や splice などの余分な操作も不要になります。

コード例

const str1 = 'sjkfampeflef';
const str2 = 'sample';

const checkConvertibility = (str1 = '', str2 = '') => {
   // どちらかが空なら形成できない
   if (!str1 || !str2) {
      return false;
   }
   let i = 0; // str2 側のポインタ
   for (let j = 0; j < str1.length && i < str2.length; j++) {
      if (str1[j] === str2[i]) {
         i++;
      }
   }
   // str2 の最後まで到達できれば部分列
   return i === str2.length;
};

console.log(checkConvertibility(str1, str2));

出力

true

注意点

indexOf や includes で「その文字が存在するか」だけを確認する実装では、並び順が崩れるケース(例：'elmpsa' から 'sample' を作る場合など)を誤って true と判定してしまうおそれがあります。順序が重要な要件では、必ず上記のように順序を考慮した走査を行いましょう。

また、空文字列の扱いは仕様によって変わります。ここでは「どちらかが空なら false」としていますが、「空文字列は常に形成可能」としたい場合は冒頭のガード節を外すだけで対応できます。