สมมติว่ามีสองสตริง A และ B เราสามารถพูดได้ว่า A หารด้วย B ลงตัว เมื่อ A ถูกสร้างขึ้นโดยการต่อ B อย่างน้อยหนึ่งครั้ง ดังนั้น ถ้า A =“abcabc” และ B =“abc” ดังนั้น A จะหารด้วย B ลงตัว ในส่วนนี้ เราจะมาดูกันว่าตัวหารร่วมมากของ string คืออะไร ส่งคืนสตริงที่ใหญ่ที่สุดที่แบ่งทั้งสองสตริง ดังนั้น หากสองสตริงคือ “ABABAB” และ “ABAB” ดังนั้น GCD จะเป็น “AB”
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- temp :=สตริงที่สั้นกว่าระหว่าง A และ B
- m :=ความยาวของอุณหภูมิ
- x :=1
- res เป็นอาร์เรย์และแทรก “” ลงใน res
- ในขณะที่ A และ B มีสตริงย่อยขนาด x จากนั้นให้เพิ่มสตริงย่อยลงใน res และเพิ่ม x ขึ้น 1
- ส่งกลับองค์ประกอบสุดท้ายในอาร์เรย์ res
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object):
def gcdOfStrings(self, str1, str2):
if len(str1)<=len(str2):
temp = str1
else:
temp = str2
m = len(temp)
x = 1
res=[""]
while x<=m:
if m%x==0 and temp[:x] * (len(str1)//x) == str1 and temp[:x] * (len(str2)//x) == str2:
res.append(temp[:x])
x+=1
return res[-1]
ob1 = Solution()
print(ob1.gcdOfStrings("ABABAB","ABAB")) อินพุต
"ABABAB" "ABAB"
ผลลัพธ์
AB
