Giả sử có hai chuỗi A và B. Ta có thể nói rằng A chia hết cho B, khi A được tạo ra bằng cách ghép B một hoặc nhiều lần. Vì vậy, nếu A =“abcabc”, và B =“abc”, thì A chia hết cho B. Trong phần này, chúng ta sẽ xem ước chung lớn nhất của một chuỗi là gì. Vì vậy, trả về chuỗi lớn nhất chia cả hai chuỗi. Vì vậy, nếu hai chuỗi là "ABABAB" và "ABAB", thì GCD sẽ là "AB"
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
- temp:=chuỗi ngắn hơn giữa A và B
- m:=độ dài của nhiệt độ
- x:=1
- res là một mảng và chèn “” vào res
- trong khi A và B có chuỗi con có kích thước x, sau đó thêm chuỗi con vào res và tăng x lên 1
- cuối cùng trả về phần tử cuối cùng trong mảng res.
Ví dụ
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
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")) Đầu vào
"ABABAB" "ABAB"
Đầu ra
AB