- Notifications
You must be signed in to change notification settings - Fork 1.3k
/
Copy path_1071.java
65 lines (60 loc) · 2.26 KB
/
_1071.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
packagecom.fishercoder.solutions.secondthousand;
publicclass_1071 {
publicstaticclassSolution1 {
publicStringgcdOfStrings(Stringstr1, Stringstr2) {
if (str1.isEmpty() || str2.isEmpty()) {
return"";
}
StringcommomDivisor = str2;
while (commomDivisor != null && !commomDivisor.isEmpty()) {
if (isDivisor(str1, commomDivisor)) {
returncommomDivisor;
} else {
commomDivisor = findNextShorterCommonDivisor(str2, commomDivisor);
}
}
return"";
}
privateStringfindNextShorterCommonDivisor(Stringstr2, StringcommomDivisor) {
intlength = nextPossibleLength(str2, commomDivisor.length() - 1);
while (length > 1) {
if (isDivisor(str2, length)) {
returnstr2.substring(0, length);
}
length = nextPossibleLength(str2, length - 1);
}
returnnull;
}
privatebooleanisDivisor(Stringstr2, intlength) {
StringcommonDivisorCandidate = str2.substring(0, length);
for (inti = 0; i < str2.length() - length; i += length) {
if (!str2.substring(i, i + length).equals(commonDivisorCandidate)) {
returnfalse;
}
}
returntrue;
}
privatebooleanisDivisor(Stringstr1, StringcommomDivisor) {
if (str1.length() == commomDivisor.length()) {
returnstr1.equals(commomDivisor);
}
inti = 0;
for (; i < str1.length() - commomDivisor.length(); i += commomDivisor.length()) {
if (!str1.substring(i, i + commomDivisor.length()).equals(commomDivisor)) {
returnfalse;
}
}
returni == (str1.length() - commomDivisor.length());
}
privateintnextPossibleLength(Stringstr2, intbound) {
if (bound <= 0) {
return -1;
}
intlen = bound;
while (str2.length() % len != 0) {
len--;
}
returnlen;
}
}
}