🙄

LeetCode 1071. Greatest Common Divisor of Strings - 文字列の最大公約数を算出

に公開
LeetCode
tech

1071. Greatest Common Divisor of Strings

https://leetcode.com/problems/greatest-common-divisor-of-strings

文字列str1と文字列str2を共通に割れる文字列xを見つける

Instituion

前回やった共通のprefixとは同じ解き方で出来るか検討してみた。

ruby

def gcd_of_strings(str1, str2)
    str1.chars.zip(str2.chars).inject([]) do |acc, columns|
      
      if columns.uniq.size == 1
        acc << columns[0]
      else
        break acc
      end
    end.join
end

最大の共通項を見つけるため下記のテストケースでNG。最小の繰り返しの共通文字列を見つける必要があると分かる。

# str1 ="ABABAB"
# str2 ="ABAB"
# Output: "ABAB"
# Expected: "AB"

アプローチ

ブルートフォース

ruby

問題の概要がわかったのでブルートフォースで解いてみる。

  • 文字列を割り切れるかどうかの判定がされていなかったので修正が必要。
  • 文字列を割り切るとは。文字列をリピートして同じ文字列になることを確認すればよさそう。
> str1 = "ABAB"
=> "ABAB"
> str2 = "AB"
=> "AB"
> str1.size / str2.size
=> 2
> str2 * (str1.size / str2.size)
=> "ABAB"
  • 最初に文字列の共通項を見つけておいて、1文字ずつ後ろから削りながら割り切れるかどうかを確認した
  • テストケースは通るが、breakやreturnが多用されていてrubyっぽくない。
def gcd_of_strings(str1, str2)
    prefix = str1.chars.zip(str2.chars).inject([]) do |acc, columns|
      if columns.uniq.size == 1
        acc << columns[0]
      else
        break acc
      end
    end.join

    prefix.length.downto(1) do |index|
      x = prefix[0..index]
      if divide?(str1, x) && divide?(str2, x)
        return x        
      end
    end
    return ""
end

def divide?(str, x)
  return false unless str.size % x.size == 0
  str == x * (str.size / x.size)
end
  • 最初のaccumuratorを使っても結局共通項までしか算出できないので短い方の文字列を使うようにすれば十分とわかる。
  • str1[0..1]とstr1[0,1]の利用が間違っていたため修正。
    • str1[0..1]は文字列の範囲指定で、インデックス0からインデックス1までの文字を抽出
    • str1[0,1]はインデックス0から1文字だけの部分文字列を抽出(pythonのstr1[0:1]と同じ意味)
> str1 = "AA"
> str1[0..1]
=> "AA"
> str1[0,1]
=> "A"

def gcd_of_strings(str1, str2)
    [str1.size, str2.size].min.downto(1) do |index|
      x = str1[0, index]
      return x if divide?(str1, x) && divide?(str2, x)
    end
    return ""
end

def divide?(str, x)
  return false unless str.size % x.size == 0
  str == x * (str.size / x.size)
end

python

class Solution:
    def gcdOfStrings(self, str1: str, str2: str) -> str:
        def divide(str: str, x: str) -> bool:
            if (len(str) % len(x)) != 0:
                return False
            return str == x * (len(str) // len(x))
        
        length = min(len(str1), len(str2))
        for i in range(length, 0, -1):
            x = str1[:i]
            if divide(str1, x) and divide(str2, x):
                return x
        return ""

typescript

function gcdOfStrings(str1: string, str2: string): string {
    function divide(str: string, x: string): boolean {
        if (str.length % x.length != 0) return false
        return str === x.repeat(str.length / x.length)
    }

    const length: number = Math.min(str1.length, str2.length)

    for (let i = length; i >= 0; i--) {
        const x: string = str1.substring(0, i)
        if (divide(str1, x) && divide(str2, x)) {
            return x
        }
    }
    return ""
};

golang

  • 文字列の繰り返しにはstrings.Repeat()を使う
func gcdOfStrings(str1 string, str2 string) string {
    length := min(len(str1),len(str2))

    for i := length; i >= 1; i-- {
        x := str1[:i]
        if divide(str1, x) && divide(str2, x){
            return x
        }
    }
    return ""
}

func divide(str string, x string) bool {
    if len(str) % len(x) != 0 {
        return false
    }
    return str == strings.Repeat(x, len(str) / len(x))
}

数学的アプローチ

LeetCodeで紹介されていた数学的アプローチ。数学的に最大公約数(GCD)を求める。

ruby

def gcd_of_strings(str1, str2)
  return "" unless (str1 + str2) == (str2 + str1)

  len1 = str1.length
  len2 = str2.length

  gcd_len = len1.gcd(len2)

  return str1[0, gcd_len]
end

学習のポイント

  • pythonではローカル関数を使う
  • 文字列の連携にはtypescript/golangでは、*ではなくrepeat()やstrings.Repeat()を使う
  • ブルートフォースでも難しく感じた。数学的アプローチを思いついたらとても簡単にできる。

Discussion