Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Greatest Common Divisor of Strings

Problem (yeniden ifade)

t, s’i böler eğer s t’nin birkaç tekrarıysa. str1 ve str2 verildiğinde her ikisini de bölen en uzun t’yi döndür; yoksa "".

Sezgi

Ortak blok varsa str1 + str2 eşittir str2 + str1 (aynı periyot). En uzun blok uzunluğu gcd(|str1|, |str2|) — Euclid uzunluklarda, sonra o önek.

Yaklaşımlar

Uzunlukların GCD'si

Doğrulanmadı

Zaman O(n+m)Alan O(n+m)

Fikir. str1+str2 !== str2+str1 ise "". Değilse str1.slice(0, gcd(len1, len2)).

Yürüyüş. ABCABC, ABC → birleşim eşleşir, gcd(6,3)=3 → ABC. LEET, CODE → birleşim farklı → "".

Trade-off. Birleşim, her öneki denemeyi atlayan O(n+m) kontrol. GCD’nin kendisi uzunlukların log’u.

Çözüm

export function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
  const gcd = (a: number, b: number): number => {
    while (b) { const t = a % b; a = b; b = t; }
    return a;
  };
  return str1.slice(0, gcd(str1.length, str2.length));
}

export function gcdOfStrings(str1: string, str2: string): string {
  if (str1 + str2 !== str2 + str1) return "";
  const gcd = (a: number, b: number): number => {
    while (b) { const t = a % b; a = b; b = t; }
    return a;
  };
  return str1.slice(0, gcd(str1.length, str2.length));
}

Şablon bağlantısı

Math & Number Theory’nin GCD / LCM şekli: Euclid uzunluklarda, önek string gcd. LC 365 ile aynı gcd(b, a % b).

Yansıma

str1+str2 ile str2+str1 aynı değilse ortak dizgi yok. Aynıysa cevap, uzunlukların gcd’si kadar önek.
O önek her iki dizgiyi tam tekrarlamalı. Uzunlukların gcd’si 1 ise cevap en fazla bir karakter.
İkisi aynı: kendisi. Biri diğerinin tekrarı: kısa olan.