【LeetCode】 1071. Greatest Common Divisor of Strings 解答・解説【Python】

はじめに
1. ポイント
2. この記事で得られること
詳細
1. 問題
  1. 原文
  2. 内容(和訳)
2. 解答
  1. 解答1：Python,再帰
終わりに
1. 補足・参考・感想
2. 疑問が解決した方は他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

様々なカテゴリの問題をランダムにあたる方法も良いですが、

二分探索、連結リストなど、テーマを絞って集中的に解いた方が練習しやすい方は以下の記事が有用です。

テーマごとに問題を分類しました。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

ポイント

- GCD

この記事で得られること

- Greatest Common Divisor(最大公約数)の文字列版の実装

詳細

問題

原文

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"

1
2

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

Example 2:

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

1
2

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

Example 3:

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

1
2

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

Constraints:

1 <= str1.length, str2.length <= 1000

str1 and str2 consist of English uppercase letters.

内容(和訳)

二つの文字列sとtについて、「tがsを分割する」とは、s = t + … + t（つまり、tを1回以上連結したもの）が成り立つことを意味します。二つの文字列str1とstr2が与えられた場合、str1とstr2の両方を分割する最大の文字列xを返します。

※chatGPTによる翻訳

解答

解答1：Python,再帰

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        #str1かstr2のいずれかがNoneの場合
        if not str1 or not str2:
            #Noneではない方を返す
            return str1 if str1 else str2
        #str1がstr2よりも文字数が少ない場合
        elif len(str1) < len(str2):
            #str1とstr2を入れ替えて再度呼び出す
            return self.gcdOfStrings(str2, str1)
        #str2の文字数分より後のstr1の文字がstr2と一致した場合
        elif str1[: len(str2)] == str2:
            return self.gcdOfStrings(str1[len(str2) :], str2)
        #上記以外の場合は空文字を返す
        else:
            return ''