付費限定
最大共同子字串 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 (程式語言的寫法)
那麼
Support the creator with action! Pay to unlock
本篇內容共 1992 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整You currently cannot view the following content, possibly because you are not logged in or do not have permission to view the room.
82會員
417Content count
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
Pike Finance 是一個新興的流動性解決方案，透過聚合區塊鏈網路上的流動性來釋放原生資產的效用，由 Wormhole、Base Chain、Circle（USDC 發行商）共同扶植成立，並使用到 Circle 的跨鏈傳輸協
可能包含敏感內容
我始終認為，性愛是兩個人的享受，如果想要的單純是自己的滿足，那麼打手槍不是比較省時省力嗎？看到自己能夠滿足對方，心理上的滿足感有時甚至大於生理上的快感。
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２×３
人們常問：「出門旅遊，你都在玩些什麽？」哇，這問題委實問得不輕，就像有人愛問「旅遊的目的是什麽」一樣。我回答過很多次，但似乎次次都不一樣。
《地表最大家族》是一部探討醫學與道德，講述精子銀行匿名捐贈和人工生殖技術所帶來讓人意想不到的醫學狀況。導演柏瑞史蒂文森由於父母不孕所以借精生子，在柏瑞父親去世後母親才告知他的生世，柏瑞好奇他的原生父親是誰開始找尋資料卻意外發現，他可能有六百多名同個父親的兄弟姊妹，這讓他發現了精子銀行的秘密。
昨天早上老闆說, 她並沒有想要找人, 她想要挽回前天, 對我說過的話。
然而辦公室主任麗莎說, 老闆已經上網開始動作了, 意思是, 她的行為永遠不符合她說過的話。
如果不是臉皮夠厚, 自己早就甩門, 拂袖而去, 再也不要回到這個坑人又狗屁倒灶的小地方。
要不是去年被老闆抓包手機簡訊, 被她苦苦哀求留
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
重點摘要：
1.9 月降息 2 碼、進一步暗示年內還有 50 bp 降息
2.SEP 上修失業率預期，但快速的降息速率將有助失業率觸頂
3.未來幾個月經濟數據將繼續轉弱，經濟復甦的時點或是 1Q25 季底附近
近期的「貼文發佈流程 & 版型大更新」功能大家使用了嗎？
新版式整體視覺上「更加凸顯圖片」，為了搭配這次的更新，我們推出首次貼文策展 ❤️
使用貼文功能並完成這次的指定任務，還有機會獲得富士即可拍，讓你的美好回憶都可以用即可拍珍藏！
Pike Finance 是一個新興的流動性解決方案，透過聚合區塊鏈網路上的流動性來釋放原生資產的效用，由 Wormhole、Base Chain、Circle（USDC 發行商）共同扶植成立，並使用到 Circle 的跨鏈傳輸協
可能包含敏感內容
我始終認為，性愛是兩個人的享受，如果想要的單純是自己的滿足，那麼打手槍不是比較省時省力嗎？看到自己能夠滿足對方，心理上的滿足感有時甚至大於生理上的快感。
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２
（被算數）×（１０）︿（算數）
＝（被算數）立零（算數）
２０００
＝（２）立零（３）
＝（２）×（１０）︿（３）
（１０）＝（１）立零（１）
（２００）＝（２）立零（２）
（６０００）＝（６）立零（３）
２００×３０＝６０００
（２）立零（２）×（３）立零（１）
＝（２×３
人們常問：「出門旅遊，你都在玩些什麽？」哇，這問題委實問得不輕，就像有人愛問「旅遊的目的是什麽」一樣。我回答過很多次，但似乎次次都不一樣。
《地表最大家族》是一部探討醫學與道德，講述精子銀行匿名捐贈和人工生殖技術所帶來讓人意想不到的醫學狀況。導演柏瑞史蒂文森由於父母不孕所以借精生子，在柏瑞父親去世後母親才告知他的生世，柏瑞好奇他的原生父親是誰開始找尋資料卻意外發現，他可能有六百多名同個父親的兄弟姊妹，這讓他發現了精子銀行的秘密。
昨天早上老闆說, 她並沒有想要找人, 她想要挽回前天, 對我說過的話。
然而辦公室主任麗莎說, 老闆已經上網開始動作了, 意思是, 她的行為永遠不符合她說過的話。
如果不是臉皮夠厚, 自己早就甩門, 拂袖而去, 再也不要回到這個坑人又狗屁倒灶的小地方。
要不是去年被老闆抓包手機簡訊, 被她苦苦哀求留
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過
親愛的阿爸天父：
最近剛讀完《迷上麻煩的耶穌》，書上提到要對祢向我們說話的方式保持開放的態度（很抱歉忘了書上是怎麼說的），祢向作者說話的方式是讓他不斷看見心型的東西，直到他最後厭倦了為止。看到能與祢相遇這麼酷的方法，當然我也要嚕，所以我也向祢禱告。
那天在浴室裡，我祈求祢讓我經歷祢的愛，腦海立刻閃過