我在这里尝试了这个问题:如何确定字符串的最小公约数?
我认为我有正确的实现,但我不确定时间和空间的复杂性。看起来两者都是线性的。然而,第一个 for 循环检查的时间复杂度让我感到困惑。 StringBuilder 的空间复杂度也很棘手。
这是我编码的内容:
public static void main(String[] args) {
String s1 = "bcdbcdbcdbcd", t1 = "bcdbcd";
String s2 = "bcdbcdbcd", t2 = "bcdbcd";
String s3 = "lrbb", t3 = "lrbb";
System.out.println(getLength(s1, t1));
System.out.println(getLength(s2, t2));
System.out.println(getLength(s3, t3));
}
private static int getLength(String s, String t) {
if(s.length() % t.length() > 0)
return -1;
StringBuilder sb = new StringBuilder();
for(int i=0;i*t.length() < s.length();i++) {
sb.append(t);
}
if(!sb.toString().equals(s))
return -1;
int divisible = 1;
for(int i=1;i<=t.length();i++) {
if(t.length()%divisible++ != 0) {
continue;
}
sb = new StringBuilder();
String subStr = t.substring(0, i);
while(sb.length() < t.length()) {
sb.append(subStr);
}
if(sb.toString().equals(t))
return i;
}
return -1;
}
当前实现的复杂性:
设 n=|s|,m=|t|
时间:
O(n/m+m^2)
空间:
O(n+m)
这是一个用Python编写的,时间复杂度为O(n*m):
def divisiblestrs(s: str, t: str)->int:
if len(t) == 0 or len(s) == 0 or len(t) > len(s) or len(s) % len(t):
return -1
i = 0
while i < len(s):
if i+len(t) <= len(s) and s[i:i+len(t)] == t:
i += len(t)
#print(f"{i=}")
continue
break
if i != len(s):
return -1
return 1
if __name__ == "__main__":
s = "bcdbcdbcdbcd"
t = "bcdbcd"
found = False
for i in range(1,len(t)):
if divisiblestrs(s, t[:i]) == 1:
print(f"String {t[:i]} of {len(t[:i])} length is the smallest divisble string between \"{s}\" and \"{t}\"")
found = True
break
if not found:
print(f"String {s} is not divisible by {t}")