1071. Greatest Common Divisor of Strings (Easy)

Question

For strings S and T, we say “T divides S” if and only if S = T + ... + T (T concatenated with itself 1 or more times)

Return the largest string X such that X divides str1 and X divides str2.

Example 1

1
2

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

Example 2

1
2

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

Example 3

1
2

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

Note:

1. 1 <= str1.length <= 1000
2. 1 <= str2.length <= 1000
3. str1[i] and str2[i] are English uppercase letters.

分析/解題

給定兩字串，找出能「除盡」這兩個字串的最長字串X。
題目已經給定的非常明顯了就是在求gcd(最大公因數)，
因此，拿出小學就教過的輾轉相除法即可。
(要看起來厲害一點的話，也可以叫歐幾里得算法Euclidean algorithm)

輾轉相除法告訴我們說，兩個數的最大公因數，
就是不斷將大的除以小的，取出餘數替代之，直到能夠整除為止。
於是這邊變成字串時，我們的除就會比較麻煩一點。
為求簡單起見，我們可以固定將第一個字串選擇放比較長的 ，
如果發現相反 的話，則將兩者進行對調 。

所以就可以分成以下的步驟：

1. 取兩字串長l1, l2，若l1 < l2 則呼叫遞迴將str1, str2交換
2. 若str1和str2完全一樣，則回傳str1
3. 若str1的前面的部分 和str2 一樣，則將str1扣除掉該部份 以後，
   呼叫遞迴傳入繼續計算。
   (因為我們操作字串的除只能一組一組扣掉 )
4. 否則就回傳空字串 (因為不一樣的話代表完全沒有共同的字串，
   跟數字的最大公因數是1概念一樣)

Java

Java的部分，字串相等請使用equals來比較，
而前面的部分一樣可以用startsWith函式，
並留意空字串要用雙引號，不能用單引號(因為單引號是char)。

Python

Python的部分，使用==和串列取值的方式，
可以簡單達成我們所需要的操作。

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(l1+l2)/O(l1+l2)，由於每階段會固定消去最小單位的長度，
所以最差的狀況就是全部都消去，也就做了兩字串長度的消去的動作，
但中間未考慮比較是否相等的狀況。
空間複雜度的部分，
Java的substring和Python的切list的方式都會產生新的單位，
理論上仍然最少會佔用到完整的l1+l2單位空間)

相似及延伸

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~

感謝大家對這系列文章的支持！這邊跟大家自我工商一下：

筆者開設的系列同名線上課程：
「從Leetcode學演算法｜基礎篇」已經上線啦！ 在這堂課中，你將學會利用十種演算法/資料結構來優化解題過程，
並實際完整練習20題 精選考古題，
進而逐漸提升到不需提示也可以突破白板題，取得工作門票！
Medium優惠(額滿即截止)： https://hiskio.com/courses/319?promo_code=VEQZV7E