旭的小窝

1071. Greatest Common Divisor of Strings

 
  • 2023年 06月28日

Promble

link: https://leetcode.com/problems/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.

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

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

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

Approach 1

Thought

use python math.gcd API.

Code

import math 

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        
        # check if they have non-zero GCD string 
        if str1 + str2 != str2 + str1:
            return '' 

        # get the GCD from math.gcd api
        max_len = math.gcd(len(str1), len(str2))
        return str1[:max_len]

Approach 2

split str into small str and compare with themself.

Thought

  1. first we need to keep the str2 > str1.
  2. def L, S:int is the lenght of str1 and str2.
  3. loop i in range(S, 0, -1) # from last to front.
    1. judge if (L/i) == int(L/i) and (S/i) == int(S/i) # this step make sure that str dont repeat.
    2. def c:str = str2[:i] # because the str2 is the min string.
    3. judge if c*int(L/i) == str1 and c*int(S/i) == str2: return c # repeat session
  4. return ‘’

Code

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        if len(str1) < len(str2):
            str1, str2 = str2, str1 

        L, S = len(str1), len(str2)

        for i in range(S, 0, -1):
            if (L/i) == int(L/i) and (S/i) == int(S/i):
                c = str2[:i]
                if c*int(L/i) == str1 and c*int(S/i) == str2:
                    return c 

        return ""
搜索