Greatest Common Divisor ของสตริงใน Python

ให้สตริง A และ B ว่า A หาร B ลงตัว (divisible) เมื่อ A สร้างได้จากการต่อ B ซ้ำ 1 ครั้งขึ้นไป เช่น A="abcabc", B="abc" หารลงตัว หา Greatest Common Divisor (GCD) ของสตริง 2 ตัว คือ สตริงยาวที่สุดที่หารทั้งคูลงตัว

ตัวอย่าง: "ABABAB" และ "ABAB" GCD = "AB"

ขั้นตอนการแก้ปัญหา

1. เลือกสตริงสั้นกว่าเป็น temp
2. วนลูปความยาว x จาก 1 ถึง len(temp):
   • ถ้า len(temp) หาร x ลงตัว และ temp[:x] ซ้ำแล้วได้ทั้ง str1 และ str2 ให้เก็บเป็น candidate
3. คืน candidate สุดท้าย (ยาวที่สุด)

ตัวอย่างโค้ด

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

วิธีแก้แบบ Euclidean Algorithm (มีประสิทธิภาพมากกว่า)

def gcdOfStrings(str1, str2):
    # ถ้าต่อกันไม่เท่ากัน ไม่มี GCD
    if str1 + str2 != str2 + str1:
        return ""
    # หา GCD ของความยาว
    from math import gcd
    return str1[:gcd(len(str1), len(str2))]

หลักการ: ถ้าสตริงทั้งสองมี common divisor ต้องเป็นไปได้ว่า str1+str2 == str2+str1 GCD ของสตริง = prefix ความยาว gcd(len1, len2)