Greatest Common Divisor of Strings
Görev tanımı
Problem
s, t'nin art arda bir ya da daha fazla kez yazılmasıysa bir t string'i bir s string'ini böler. İki string a ve b verildiğinde, ikisini de bölen en uzun string'i döndür; hiçbir string bölmüyorsa boş string döndür.
Örnekler
Input: a = "ABCABC", b = "ABC"
Output: "ABC"
Input: a = "ABABAB", b = "ABAB"
Output: "AB"
Neden: AB ikisini de böler, ABAB ise ABABAB'yi bölmez
Input: a = "LOOP", b = "POOL"
Output: ""
Neden: edge case: string'lerin hiç ortak tekrar birimi yok
İpuçları
0 / 3
Ortak bir t böleni varsa iki string de t'nin kopyalarından oluşur. İki string'i iki sırada yapıştırınca ne olur?
a + b, tam olarak iki string de aynı birimden kurulduğunda b + a'ya eşittir. İkisi farklıysa cevap boştur.
a + b == b + a olduğunda en uzun ortak bölenin uzunluğu gcd(len(a), len(b))'dir ve o, basitçe a'nın o uzunluktaki prefix'idir.
- Hedef zaman
- O(len(a) + len(b))
- Hedef alan
- O(len(a) + len(b))
Çözüm
İki string de bir t biriminin kopyalarıysa a + b ile b + a aynı sayıda t kopyasıdır, yani eşittirler; string'ler ortak bir birimden kurulmamışsa iki birleştirme bir yerde farklılaşır ve o tek karşılaştırma bu durumu dışarıda bırakır. Bir birimi paylaştıklarında her ortak bölenin uzunluğu iki uzunluğu da böler; mümkün olan en uzun uzunluk, yani iki uzunluğun en büyük ortak böleni (EBOB) de işe yarar, çünkü o uzunluktaki bir prefix (önek) iki string'i de döşer. Öklid algoritması onu O(log n) adımda hesaplar; birleştirme kontrolü için bütün çözüm O(n + m) zaman ve O(n + m) alana mal olur.
from math import gcd
def gcd_of_strings(a, b):
if a + b != b + a: # no common building block exists
return ""
return a[:gcd(len(a), len(b))] # the longest block that tiles both
print(gcd_of_strings("ABCABC", "ABC")) # -> ABC
print(gcd_of_strings("ABABAB", "ABAB")) # -> AB
print(gcd_of_strings("LOOP", "POOL")) # -> (empty string)Kodda değil de fikirde mi takıldın? EBOB ve Öklid bunu anlatıyor.