1071. Greatest Common Divisor of Strings

[fockspaces]

判斷最大共同子串 一開始先找 gcd，然後用 gcd_str 判斷是否為這兩個的共同子串，是的話 True, 否則 False

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def is_substring(str, substr):
            len_substr = len(substr)
            if not str:
                return True
            return str[:len_substr] == substr and is_substring(str[len_substr:], substr)

        gcd = math.gcd(len(str1), len(str2))
        gcd_str = str1[:gcd]
        return str1[:gcd] if is_substring(str1, gcd_str) and is_substring(str2, gcd_str) else ""

[fockspaces]

GPT solution: 優化了先前用 recursion 比較的方式，因為要成為 gcd_substr 必定為倍數關係 直接乘固定比例去比較字串即可

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        gcd = math.gcd(len(str1), len(str2))
        gcd_str = str1[:gcd]
        if gcd_str * (len(str1) // gcd) == str1 and gcd_str * (len(str2) // gcd) == str2:
            return gcd_str
        return ""

[fockspaces]

最佳解：

1. 利用回文特性，A + B = B + A 才有機會成為出現 gcd_substr
2. 如果確認回文，直接找 gcd 定長 substr 即可

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        // Check if concatenated strings are equal or not, if not return ""
        if(str1 + str2 != str2 + str1)
            return "";
        // If strings are equal than return the substring from 0 to gcd of size(str1), size(str2)
        return str1.substr(0, gcd(str1.size(), str2.size()));
    }
};