最大共同子字串 Greatest Common Divisor of Strings_Leetcode 精選75題解析

Hill Country Camera null on Unsplash

題目敘述

題目會給定兩個輸入字串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個字元之間。

• str1 and str2 consist 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 (程式語言的寫法)