Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2023-02-01 11:47:06
1071. Greatest Common Divisor of Strings
你給兩個字串,求出它們的最大共通整除字串,若一個字串s可以被字串t整除,則s滿足:
s = t + t + .. + t
Example:
Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Input: str1 = "LEET", str2 = "CODE"
Output: ""
思路:
1.若s1和s2存在字串t可以整除他,那麼s1 = n*t 且 s2 = m*t 因為它們全為t所組成
所以 s1 + s2 = (n+m)*t,因為組合後的字串只會有t所以 s1+s2 和 s2+s1 必定是
相同的字串,如果不相等就直接返回。
2.因為組合後的字串只有t所以可以把他簡化為求最大工因數的問題,用碾轉相除法得
到gcd後,返回長度為gcd的子字串即可。
Java Code:
作者: MurasakiSion (紫咲シオン)   2023-02-01 11:49:00
大師
作者: a1234555 (肉寶寶)   2023-02-01 11:51:00
大師
作者: pandix (麵包屌)   2023-02-01 12:02:00
大師

Links booklink

Contact Us: admin [ a t ] ucptt.com