JavaScriptで文字列の一部を並べ替えて別の文字列を形成できるか判定する方法

問題

2つの文字列 str1 と str2 を引数に受け取るJavaScript関数を作成する必要があります。str1 に含まれる文字の一部を使い、並べ替えることで str2 と一致する文字列を形成できる場合は true を、そうでない場合は false を返すようにします。

たとえば、str1 が "rkqodlw"、str2 が "world" の場合、str1 内に必要な文字がすべて揃っているため、結果は true になります。

解法の考え方

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

1. まず、str1 の長さが str2 よりも短い場合は、どんなに並べ替えても str2 を形成できないため、即座に false を返します。
2. str2 を1文字ずつ配列に分解し、「まだ見つかっていない必要な文字」のリストとして管理します。
3. str1 の各文字を順に調べ、必要な文字リストに含まれていれば、その文字をリストから削除（消費）します。
4. 最終的にリストが空になっていれば、str1 の一部の文字だけで str2 を完全に形成できたことになります。

コード例

以下が実際のコードです。

const str1 = 'rkqodlw';
const str2 = 'world';

const canForm = (str1 = '', str2 = '') => {
  if(str1.length < str2.length){
    return false;
  }
  const res = str2.split('');
  str1.split('').forEach(val => {
    if(res.includes(val)){
      res.splice(res.indexOf(val), 1);
    }
  });
  return res.length === 0;
};

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

出力

コンソールには以下のように表示されます。

true

処理の流れの解説

このコードでは、str2.split('') によって "world" が ['w', 'o', 'r', 'l', 'd'] という配列に変換されます。その後、str1 の各文字を順番にチェックし、配列内に同じ文字が存在すれば splice() メソッドで取り除いていきます。

すべての処理が完了した時点で res 配列が空（res.length === 0）であれば、str2 のすべての文字が str1 内から見つかったことを意味するため、true を返します。

なお、この実装の計算量は O(n × m)（n は str1 の長さ、m は str2 の長さ）です。パフォーマンスを重視する場合は、両方の文字列の文字出現回数をオブジェクトやMapでカウントして比較する方式に書き換えると、O(n + m) まで高速化できます。