【JavaScript】文字列を繰り返して別の文字列を形成できる最小回数を求める方法

問題

2つの文字列 str1 と str2 を第1引数・第2引数として受け取るJavaScript関数を作成する必要があります。

この関数は、str1 を繰り返し連結していったときに str2 がその部分文字列となる、最小の繰り返し回数を返します。何度繰り返しても str2 が部分文字列にならない場合は -1 を返してください。

たとえば、関数に次の入力を与えたとします。

入力：

const str1 = 'wxyz';
const str2 = 'yzwxyzwx';

出力：

const output = 3;

出力の説明：

str1（wxyz）を3回繰り返した文字列 wxyzwxyzwxyz の中には、yzwxyzwx が部分文字列として含まれています。2回以下の繰り返しでは実現できないため、正解は 3 となります。

コード例

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

const str1 = 'wxyz';
const str2 = 'yzwxyzwx';

const countRepeat = (str1 = '', str2) => {
  let i = 1;
  let current = str1;
  while (true) {
    // 現在の連結結果に str2 が含まれているかチェック
    if (current.indexOf(str2) >= 0) {
      return i;
    }
    // これ以上繰り返しても見つからないと判断できるケース
    if (current.length > str2.length * 2 && i > 2) {
      return -1;
    }
    current += str1;
    i += 1;
  }
};

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

出力

3

コードの解説

このアルゴリズムのポイントは次の3点です。

• 繰り返し回数の管理：変数 i で現在の繰り返し回数を記録し、変数 current に str1 を連結した文字列を保持します。
• 一致の判定：indexOf() を使って、current の中に str2 が含まれるかどうかを毎ループで確認します。見つかった時点で、そのときの繰り返し回数 i を返します。
• 打ち切り条件：current の長さが str2 の長さの2倍を超え、かつすでに2回以上繰り返しているのに一致しない場合は、これ以上繰り返しても新たに見つかる可能性がないため、-1 を返して処理を終了します。

無限ループを回避するための適切な打ち切り条件を設けることが、この種の文字列操作問題を実装するうえでの重要なポイントです。