【JavaScript】文字列が配列内の文字列の組み合わせで構成できるか判定する方法

概要

本稿では、第1引数に文字列の配列、第2引数に判定対象の文字列を受け取るJavaScript関数を作成します。この関数は、第2引数の文字列が、配列内の文字列を任意の順序で組み合わせることで完全に構成できる場合に true を返すものです。

まず、具体的な例を見てみましょう。入力となる配列が次の通りです。

const arr = ['for', 'car', 'keys', 'forth'];

そして、判定対象の文字列がこちらです。

const str = 'forthcarkeys';

この場合、出力は true になります。「forthcarkeys」という文字列は、配列のインデックス3の「forth」、インデックス1の「car」、インデックス2の「keys」を連結したものと一致するためです。

サンプルコード

実装の流れは大きく分けて2段階です。まず indexOf() を使って、配列内の各文字列が対象文字列のどの位置に出現するかをすべて洗い出します。続いて再帰処理により、各候補を「使う／使わない」のパターンで全探索し、文字列を余りなく埋め尽くせる組み合わせが存在するかを確認します。

const arr = ['for', 'car', 'keys', 'forth'];
const str = 'forthcarkeys';

const checkPossibility = (str = '', arr = []) => {
   // 配列内の各文字列が対象文字列に出現する位置をすべて収集する
   let possibilities = arr.reduce(function (r, a) {
      let p = str.indexOf(a);
      while (p !== -1) {
         r.push({ word: a, position: p });
         p = str.indexOf(a, p + 1);
      }
      return r;
   }, []);

   // 再帰的に「単語を使う／使わない」パターンを全探索する
   const findRecursively = (i, t) => {
      let s = t.slice();
      // 候補をすべて検討し終えたら、未使用の文字が残っていないか確認
      if (i === possibilities.length) {
         return !t.join('');
      }
      // 単語を置こうとする位置の文字がすべて未使用であれば、使用済みとしてマーク
      if (possibilities[i].word.split('').every(function (c, j) {
         return s[j + possibilities[i].position] !== '';
      })) {
         for (let j = 0; j < possibilities[i].word.length; j++) {
            s[j + possibilities[i].position] = '';
         }
         // この単語を採用したケースを試す
         if (findRecursively(i + 1, s)) {
            return true;
         }
      }
      // この単語を採用しなかったケースも試す
      return findRecursively(i + 1, t);
   };
   return findRecursively(0, str.split(''));
};

console.log(checkPossibility(str, arr));

実行結果

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

true

処理のポイント

• 候補の収集： reduce() と indexOf() を組み合わせ、各文字列が対象文字列内に出現するすべての位置を記録します。
• 再帰による全探索： 各候補ごとに「採用する」「採用しない」の2通りを再帰的に試行し、成功する組み合わせが1つでも見つかれば true を返します。
• 文字の二重使用を防止： 採用した単語に該当する部分は空文字でマークされるため、同じ位置の文字が別の単語に再利用されることはありません。