সমস্যা বিবরণ
দুটি স্ট্রিং A এবং B দেওয়া আছে। A, B দিয়ে বিভাজ্য যদি A = B + B + ... (এক বা একাধিকবার) হয়। দুটি স্ট্রিংর সবচোয়ে বড় কমন ডিভাইজর (GCD স্ট্রিং) বের করতে হবে।
উদাহরণ: "ABABAB" এবং "ABAB" → GCD = "AB"। কারণ "AB"+"AB"+"AB" = "ABABAB" এবং "AB"+"AB" = "ABAB"।
সমাধানের পদ্ধতি
- ছোট স্ট্রিংটিকে temp ধরে রাখুন।
- temp-এর সব সম্ভাব্য প্রিফিক্স (লেন্থ ১ থেকে len(temp)) চেক করুন।
- প্রিফিক্সটি যদি দুটি স্ট্রিংই তৈরি করতে পারে (রিপিট করে), তবে সেটি ক্যান্ডিডেট।
- সবচোয়ে বড় ক্যান্ডিডেট ফেরত দিন।
পাইথন উদাহরণ
class Solution(object):
def gcdOfStrings(self, str1, str2):
if len(str1) <= len(str2):
temp = str1
else:
temp = str2
m = len(temp)
res = [""]
for x in range(1, m + 1):
if m % x == 0:
candidate = temp[:x]
if candidate * (len(str1) // x) == str1 and candidate * (len(str2) // x) == str2:
res.append(candidate)
return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB", "ABAB"))
ইনপুট
"ABABAB" "ABAB"
আউটপুট
AB
গাণিতিক পদ্ধতি (O(n+m)) - ইউক্লিডিয়ান অ্যালগরিদম
def gcdOfStrings(str1, str2):
# GCD স্ট্রিং আছে কিনা চেক: str1+str2 == str2+str1 হলে মাত্র
if str1 + str2 != str2 + str1:
return ""
# স্ট্রিং লেন্থের GCD বের করুন
from math import gcd
gcd_len = gcd(len(str1), len(str2))
return str1[:gcd_len]
