付費限定
最大共同子字串 Greatest Common Divisor of Strings_Leetcode 精選75題解析
閱讀時間約 4 分鐘
題目敘述
題目會給定兩個輸入字串str1和str2，要求我們找出這兩個字串的最大共同子字串。
如果無解，則返回空字串""。
測試範例
Example 1:
Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Example 2:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Example 3:
Input: str1 = "LEET", str2 = "CODE"
Output: ""
約束條件
Constraints:
1 <= str1.length, str2.length <= 1000
str1 和 str2的字串長度都介於1~1000個字元之間。
str1andstr2consist of English uppercase letters.
str1 和 str2 都只會有大寫英文字幕。
演算法
這題有點像以前求兩數之間的最大公因數GCD的變化題，這題改成問兩個字串的最大共同子字串。
比較困難的地方，在於兩個字串未必存在共同子字串，有可能無解，要怎麼判斷呢?
其實，我們可以這樣想，假設str1和str2有共同子字串k，分別重複a次和b次。
所以，字串str1可以寫成
str1 = k ... k 重複a次 = a * k (程式語言的寫法)
字串str2可以寫成
str2 = k ... k 重複b次 = b * k (程式語言的寫法)
那麼
以行動支持創作者！付費即可解鎖
本篇內容共 1992 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
88會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Hi 大家好，我是Ethan😊
相近大家都知道保濕是皮膚保養中最基本，也是最重要的一步。無論是在畫室裡長時間對著畫布，還是在旅途中面對各種氣候變化，保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水，還能提升後續保養品的吸收效率。
曾經，我的保養程序簡單到只包括清潔和隨意上乳液
Pike Finance 是一個新興的流動性解決方案，透過聚合區塊鏈網路上的流動性來釋放原生資產的效用，由 Wormhole、Base Chain、Circle（USDC 發行商）共同扶植成立，並使用到 Circle 的跨鏈傳輸協
可能包含敏感內容
我始終認為，性愛是兩個人的享受，如果想要的單純是自己的滿足，那麼打手槍不是比較省時省力嗎？看到自己能夠滿足對方，心理上的滿足感有時甚至大於生理上的快感。
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２×３
人們常問：「出門旅遊，你都在玩些什麽？」哇，這問題委實問得不輕，就像有人愛問「旅遊的目的是什麽」一樣。我回答過很多次，但似乎次次都不一樣。
《地表最大家族》是一部探討醫學與道德，講述精子銀行匿名捐贈和人工生殖技術所帶來讓人意想不到的醫學狀況。導演柏瑞史蒂文森由於父母不孕所以借精生子，在柏瑞父親去世後母親才告知他的生世，柏瑞好奇他的原生父親是誰開始找尋資料卻意外發現，他可能有六百多名同個父親的兄弟姊妹，這讓他發現了精子銀行的秘密。
昨天早上老闆說, 她並沒有想要找人, 她想要挽回前天, 對我說過的話。
然而辦公室主任麗莎說, 老闆已經上網開始動作了, 意思是, 她的行為永遠不符合她說過的話。
如果不是臉皮夠厚, 自己早就甩門, 拂袖而去, 再也不要回到這個坑人又狗屁倒灶的小地方。
要不是去年被老闆抓包手機簡訊, 被她苦苦哀求留
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Hi 大家好，我是Ethan😊
相近大家都知道保濕是皮膚保養中最基本，也是最重要的一步。無論是在畫室裡長時間對著畫布，還是在旅途中面對各種氣候變化，保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水，還能提升後續保養品的吸收效率。
曾經，我的保養程序簡單到只包括清潔和隨意上乳液
Pike Finance 是一個新興的流動性解決方案，透過聚合區塊鏈網路上的流動性來釋放原生資產的效用，由 Wormhole、Base Chain、Circle（USDC 發行商）共同扶植成立，並使用到 Circle 的跨鏈傳輸協
可能包含敏感內容
我始終認為，性愛是兩個人的享受，如果想要的單純是自己的滿足，那麼打手槍不是比較省時省力嗎？看到自己能夠滿足對方，心理上的滿足感有時甚至大於生理上的快感。
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２×３
人們常問：「出門旅遊，你都在玩些什麽？」哇，這問題委實問得不輕，就像有人愛問「旅遊的目的是什麽」一樣。我回答過很多次，但似乎次次都不一樣。
《地表最大家族》是一部探討醫學與道德，講述精子銀行匿名捐贈和人工生殖技術所帶來讓人意想不到的醫學狀況。導演柏瑞史蒂文森由於父母不孕所以借精生子，在柏瑞父親去世後母親才告知他的生世，柏瑞好奇他的原生父親是誰開始找尋資料卻意外發現，他可能有六百多名同個父親的兄弟姊妹，這讓他發現了精子銀行的秘密。
昨天早上老闆說, 她並沒有想要找人, 她想要挽回前天, 對我說過的話。
然而辦公室主任麗莎說, 老闆已經上網開始動作了, 意思是, 她的行為永遠不符合她說過的話。
如果不是臉皮夠厚, 自己早就甩門, 拂袖而去, 再也不要回到這個坑人又狗屁倒灶的小地方。
要不是去年被老闆抓包手機簡訊, 被她苦苦哀求留
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過