Javascriptの文字列の最大公約数

今日はLeetCode 75シリーズの2問目を解きました。この問題に私がどのように取り組んだかを共有したいと思います。

問題の説明:
2 つの文字列、str1 と str2 が与えられています。 x が str1 と str2 の両方を分割するような最大の文字列 x を返します。

例:

入力: str1 = "ABCABC"、str2 = "ABC"
出力: "ABC"

入力: str1 = "ABABAB"、str2 = "ABAB"
出力: "AB"

入力: str1 = "LEET"、str2 = "CODE"
出力: ""
**
私のアプローチ**

私はソリューションを 3 つの部分に分割しました:

公約数文字列が存在するかどうかを確認します:
まず、str1 str2 と str2 str1 を連結して公約数が存在するかどうかを確認します。

連結された 2 つの文字列が等しくない場合、公約数がないことを意味し、関数は空の文字列 ("") を返します。

GCD 長を求める:
次に、str1 と str2 の長さの最大公倍数を求めます。

私は再帰的な gcd() 関数を使用します。 b !== 0 の場合、関数は 2 つの引数を使用してそれ自体を再帰的に呼び出します:
gcd(a, b) = gcd(b, a % b)
b = 0 になると、関数は GCD の長さである a を返します。

計算例:

初期呼び出し: gcd(6, 3)
b = 3 は 0 ではないので、 gcd(3, 6 % 3) → gcd(3, 0)

2 番目の呼び出し: gcd(3, 0)
b = 0 なので、関数は 3 を返します。

GCD 部分文字列を抽出します:
最後に、gcdlength を使用して str1 から部分文字列を抽出します。

function gcdOfStrings(str1, str2) {
  // recursive function to calculate the GCD of two numbers
  function gcd(a, b) {
    console.log(a, b);
    return b === 0 ? a : gcd(b, a % b);
  }

  // Step 1: Check if str1 and str2 match or not
  if (str1 + str2 !== str2 + str1) {
    return ""; // No common pattern exists
  }

  // Step 2: Find the GCD of the lengths of str1 and str2
  const len1 = str1.length;
  const len2 = str2.length;
  const gcdLength = gcd(len1, len2);

  // Step 3: The largest divisor substring
  return str1.substring(0, gcdLength);
}

// Example usage:
console.log(gcdOfStrings("ABCABC", "ABC")); // Output: "ABC"
console.log(gcdOfStrings("ABABAB", "ABAB")); // Output: "AB"
console.log(gcdOfStrings("LEET", "CODE")); // Output: ""

より良い解決策やアイデアがある場合は、お気軽に私と共有してください。

以上がJavascriptの文字列の最大公約数の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。