用于查找 2 个字符串的最小公约数的运行时

问题描述 投票:0回答:2

我在这里尝试了这个问题:如何确定字符串的最小公约数?

我认为我有正确的实现,但我不确定时间和空间的复杂性。看起来两者都是线性的。然而,第一个 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;
}
java string time-complexity big-o space-complexity
2个回答
0
投票

当前实现的复杂性:

设 n=|s|,m=|t|

时间:

O(n/m+m^2)

空间:

O(n+m)

0
投票

这是一个用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}")
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.