1071.Greatest Common Divisor of Strings

tags: Easy,Math,String

1071. Greatest Common Divisor of Strings

題目描述

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

範例

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"

Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"

Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Constraints:

• 1 <= str1.length, str2.length <= 1000
• str1 and str2 consist of English uppercase letters.

解答

C++

思路

• 如果gcdString存在，也就是兩個字串都是由gcdString組成，則這兩個字串無論先後，相加起來的結果一定相同。
• 所有的cdString也會是gcdString的一部分，因此直接針對兩個字串長度取最大公因數就好。

class Solution {
public:
    string gcdOfStrings(string str1, string str2) {
        return str1 + str2 == str2 + str1 ? str1.substr(0, gcd(str1.size(), str2.size())): "";
    }
};

Yen-Chi ChenWed, Feb 1, 2023

Python

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        return str1[:gcd(len(str1), len(str2))] if str1 + str2 == str2 + str1 else ""

Yen-Chi ChenWed, Feb 1, 2023

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        n = min(len(str1), len(str2))
        gcd = ''
        while n != 0:
            if len(str1) % n == 0 and len(str2) % n == 0:
                gcd = str1[0:n]
                print(n, len(str1), len(str2))
                #check str1
                flag1 = (str1 == gcd*(len(str1)//n) )
                #check str2
                flag2 = (str2 == gcd*(len(str2)//n) )

                if flag1 and flag2:
                    return str1[:n]
                else:
                    n -= 1
            else:
                n -= 1
        return ""

玉山

Reference

回到題目列表