-
-
Notifications
You must be signed in to change notification settings - Fork 300
/
686.java
92 lines (79 loc) · 2.65 KB
/
686.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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
__________________________________________________________________________________________________
sample 1 ms submission
// 686
public class Solution {
public int repeatedStringMatch(final String A, final String B) {
final int aL = A.length();
final int bL = B.length();
if (aL >= bL) {
if (A.indexOf(B) != -1) {
return 1;
} else {
return (A + A).indexOf(B) == -1 ? -1 : 2;
}
}
if (B.indexOf(A) == -1) {
return (A + A).indexOf(B) == -1 ? -1 : 2;
}
int res = 0;
int idx = B.indexOf(A);
if (idx > 0) {
if (A.indexOf(B.substring(0, idx)) == -1) {
return -1;
} else {
res = 1;
}
}
final int lastExpectedIdx = ((B.length() - idx) / aL) * aL;
for (int i = idx; i < lastExpectedIdx; i += aL) {
idx = B.indexOf(A, i);
if (idx != i) {
return -1;
}
res++;
}
if (idx + aL == bL) {
return res;
}
if (A.indexOf(B.substring(idx + aL, bL)) != 0) {
return -1;
}
return res + 1;
}
public static void main(String[] args) {
System.out.println(new Solution().repeatedStringMatch("abcd", "bcdab"));
System.out.println(new Solution().repeatedStringMatch("abcd", "abcdb"));
System.out.println(new Solution().repeatedStringMatch("ab", "aba"));
System.out.println(new Solution().repeatedStringMatch("a", "ab"));
System.out.println(new Solution().repeatedStringMatch("a", "aa"));
System.out.println(new Solution().repeatedStringMatch("ab", "babababa"));
System.out.println(new Solution().repeatedStringMatch("ab", "bababab"));
System.out.println(new Solution().repeatedStringMatch("bb", "bbbbbbb"));
System.out.println(new Solution().repeatedStringMatch("ba", "bab"));
System.out.println(new Solution().repeatedStringMatch("abaa", "ba"));
}
}
__________________________________________________________________________________________________
sample 36684 kb submission
class Solution {
public int repeatedStringMatch(String A, String B) {
int limit = Math.max(A.length(), B.length());
StringBuilder repeating = new StringBuilder(A);
// check
Set<Character> setA = new HashSet();
for(char letter : A.toCharArray()) setA.add(letter);
Set<Character> setB = new HashSet();
for(char letter : B.toCharArray()) setB.add(letter);
if (setB.size() > setA.size()) return (-1);
// count
for (int i = 0; i <= limit; i++) {
if (repeating.indexOf(B) != -1) {
return (i + 1);
} else {
repeating.append(A);
}
}
return (-1);
}
}
__________________________________________________________________________________________________