1071. 字符串的最大公因子

字符串的最大公因子

题目描述

对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。

返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。

---

示例：

输入：str1 = "ABCABC", str2 = "ABC"
输出："ABC"
输入：str1 = "ABABAB", str2 = "ABAB"
输出："AB"
输入：str1 = "LEET", str2 = "CODE"
输出：""

---

提示：
1 <= str1.length <= 1000
1 <= str2.length <= 1000
str1[i] 和 str2[i] 为大写英文字母

转载来源：力扣（LeetCode）

---

题目分析

字符串的题目是我的弱项，但这道题我比较快的有了思路，并且一次就AC了，在我沾沾自喜的时候，AC结果显示我超越了20%的用户......

国际惯例，落后就去抄袭，下面我就介绍一下我自己的算法和排在前列的算法：

• 华而不实的算法

  • 先确保str1短于str2,
  • 如果str1和str2等长且相等，显然最大公因子就是自身，如果str1和str2等长且内容不等，显然没结果
  • str1短于str2，str2就砍掉str1长度，用剩下的子串和str1继续寻找公因子

  fun gcdOfStrings(str1: String, str2: String): String {
      if(str1.length > str2.length)
          return gcdOfStrings(str2,str1)
      if(str1.length == str2.length)
          when(str1 == str2){
              true->return str1
              false->return ""
          }
      val tmp = str2.substring(str1.length)
      return gcdOfStrings(str1,tmp)
  }
  

  真的是思路清晰且代码简练啊，但是和下面优秀的算法相比有致命的缺点：

  1. 字符串比较次数过多，耗时
  2. 字符串截取次数过多，耗时

  下面就介绍优秀的算法吧（留下不争气的泪水）

• 欧几里得算法
  显然，如果str1和str2有最大公因子X，那么str1可表示为AX，str2可表示为BX，str1+str2 == str2+str1 == （A+B）X （这里是字符串的相等）

1. 根据上面的定理，可以直接确定str1和str2是否有最大公因子：

           if(str1+str2 != str2+str1)
               return ""
   

2. 现在我们确保了X是存在的，那么就要求X究竟是什么（其实我们只要求出X的长度就行了，不需要求出X的具体的值，因为str1和str2都是由X构成的），X的长度实际上就是str1的长度和str2的长度的最大公因子，求最大公因子的算法我们在小学初中就接触过，叫“欧几里得算法”，也叫“辗转相除法”

       //默认len1 > len2
       fun gcd(len1: Int, len2: Int): Int {
           if(len2 == 0)
               return len1
           return gcd(len2,len1%len2)
       }
   

3. 得到X的长度后，我们就可以用subString轻松求出X来了

       fun gcdOfStrings(str1: String, str2: String): String {
           if (str1 + str2 != str2 + str1)
               return ""
           val size = when(str1.length > str2.length){
               true->gcd(str1.length, str2.length)
               false->gcd(str2.length, str1.length)
           }
           return str1.substring(0,size)
       }
   

今天，又是充满被虐的一天~