1071. Greatest Common Divisor of Strings

LeetCode 題目

LeetCode 解題連結

題目

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.

翻譯

求 str1 & str2 的最大公因數 x

Example:

Example 1:

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

Example2:

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

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

思路

一、極限值/特殊狀況

• 無

二、哪種資料結構解

數學題

三、大概會怎麼解

歐幾里德演算法

兩個有最大公因數的數字，大的一方減去小的，仍然可以被最大公因數整除。基於這個原理，持續相減直到兩個數字變成最大公因數。

如 252, 105 的最大公因數為 21，

1. 252 - 105 = 147, 147 可以被 21 整除

147 105

1. 147 - 105 = 42, 41 可以被 21 整除

42 105

1. 105 - 42 = 63, 63 可以被 21 整除

42 63

1. 63 - 42 = 21, 21 可以被 21 整除

42 21

5 42 - 21 = 21, 21 可以被 21 整除

21 21

252 105
147 105
42  105
42  63
42  21
21  21

由上述的公式去計算，如果減到最後兩個數字都變成 1，則代表沒有最大公因數。

同樣的邏輯用在尋找最大公因數的字串上，有最大公因數的兩個數字，相加也會可被整除。

if str1 + str2 !== str2 + str1，代表兩者沒有最大公因數
else if str1 === str2 代表 str1 為最大公因數
else if 遞迴相減，直到兩個字串為同樣的或沒有最大公因數

時間複雜度

0(n)

解題

var gcdOfStrings = function(str1, str2) {
    if (str1 + str2 !== str2 + str1) return ''
    else if (str1 === str2) return str1
    else if (str1.length > str2.length) return gcdOfStrings(str1.slice(str2.length), str2)
    else return gcdOfStrings(str2.slice(str1.length), str1)
};