→ MurasakiSion: 大師 02/01 11:49
推 a1234555: 大師 02/01 11:51
推 pandix: 大師 02/01 12:02
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：
--------------------------------
class Solution {
public String gcdOfStrings(String s1, String s2) {
if (!(s1 + s2).equals(s2 + s1)) {
return "";
}
int gcd = gcd(s1.length(), s2.length());
return s2.substring(0, gcd);
}
private int gcd(int x, int y) {
return x == 0 ? y : gcd(y % x, x);
}
}
--------------------------------
--
https://i.imgur.com/CBMFmWk.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.0.114 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1675223229.A.005.html