Skip to content

Commit c5433a1

Browse files
gazeldxgazeldx
committed
Update all solutions' changes in 2025-05-09.
1 parent 5822928 commit c5433a1

6 files changed

+1396
-0
lines changed

‎en/1001-2000/1071-greatest-common-divisor-of-strings.md

Lines changed: 264 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,264 @@
1+
# 1071. Greatest Common Divisor of Strings - LeetCode Python/Java/C++/JS code
2+
3+
Visit original link: [1071. Greatest Common Divisor of Strings - LeetCode Python/Java/C++/JS code](https://leetcodepython.com/en/leetcode/1071-greatest-common-divisor-of-strings) for a better experience!
4+
5+
LeetCode link: [1071. Greatest Common Divisor of Strings](https://leetcode.com/problems/greatest-common-divisor-of-strings), difficulty: **Easy**.
6+
7+
## LeetCode description of "1071. Greatest Common Divisor of Strings"
8+
9+
For two strings `s` and `t`, we say "`t` divides `s`" if and only if `s = t + t + t + ... + t + t` (i.e., `t` is concatenated with itself one or more times).
10+
11+
Given two strings `str1` and `str2`, return the **largest string** `x` such that `x` divides both `str1` and `str2`.
12+
13+
### [Example 1]
14+
15+
**Input**: `str1 = "ABCABC", str2 = "ABC"`
16+
17+
**Output**: `"ABC"`
18+
19+
### [Example 2]
20+
21+
**Input**: `str1 = "ABABAB", str2 = "ABAB"`
22+
23+
**Output**: `"AB"`
24+
25+
### [Example 3]
26+
27+
**Input**: `str1 = "LEET", str2 = "CODE"`
28+
29+
**Output**: `""`
30+
31+
### [Constraints]
32+
33+
- `1 <= str1.length, str2.length <= 1000`
34+
- `str1` and `str2` consist of English uppercase letters.
35+
36+
### [Hints]
37+
38+
<details>
39+
<summary>Hint 1</summary>
40+
The greatest common divisor must be a prefix of each string, so we can try all prefixes.
41+
42+
43+
</details>
44+
45+
## Intuition
46+
47+
The greatest common divisor must be a prefix of each string, so we can try all prefixes.
48+
49+
Enumerate all possible prefixes and check whether repeating the prefix several times can form the original strings.
50+
51+
Return the longest one that satisfies the condition.
52+
53+
54+
## Step by Step Solutions
55+
56+
1. Get the minimum length `min_size` of the two strings.
57+
2. For length `i` from `1` to `min_size`, enumerate the prefix `candidate`.
58+
3. If the length of `candidate` can divide both `str1` and `str2`, and repeating `candidate` the corresponding times equals `str1` and `str2`, update the result.
59+
4. Finally, return the longest valid `candidate`.
60+
61+
## Complexity
62+
63+
- Time complexity: `O(N * (N + M))`.
64+
- Space complexity: `O(N)`.
65+
66+
## Python
67+
68+
```python
69+
class Solution:
70+
def gcdOfStrings(self, str1: str, str2: str) -> str:
71+
result = ""
72+
min_size = min(len(str1), len(str2))
73+
74+
for i in range(1, min_size + 1):
75+
if len(str1) % i == 0 and len(str2) % i == 0:
76+
candidate = str1[:i]
77+
78+
if candidate * (len(str1) // i) == str1 and candidate * (len(str2) // i) == str2:
79+
result = candidate
80+
81+
return result
82+
```
83+
84+
## Java
85+
86+
```java
87+
class Solution {
88+
public String gcdOfStrings(String str1, String str2) {
89+
String result = "";
90+
int minSize = Math.min(str1.length(), str2.length());
91+
92+
for (int i = 1; i <= minSize; i++) {
93+
if (str1.length() % i == 0 && str2.length() % i == 0) {
94+
String candidate = str1.substring(0, i);
95+
if (isValid(candidate, str1) && isValid(candidate, str2)) {
96+
result = candidate;
97+
}
98+
}
99+
}
100+
101+
return result;
102+
}
103+
104+
private boolean isValid(String candidate, String s) {
105+
int count = s.length() / candidate.length();
106+
StringBuilder sb = new StringBuilder();
107+
for (int i = 0; i < count; i++) {
108+
sb.append(candidate);
109+
}
110+
return sb.toString().equals(s);
111+
}
112+
}
113+
```
114+
115+
## C++
116+
117+
```cpp
118+
class Solution {
119+
public:
120+
string gcdOfStrings(string str1, string str2) {
121+
string result;
122+
int min_size = min(str1.size(), str2.size());
123+
124+
for (int i = 1; i <= min_size; i++) {
125+
if (str1.size() % i == 0 && str2.size() % i == 0) {
126+
string candidate = str1.substr(0, i);
127+
if (isValid(candidate, str1) && isValid(candidate, str2)) {
128+
result = candidate;
129+
}
130+
}
131+
}
132+
133+
return result;
134+
}
135+
136+
private:
137+
bool isValid(const string& candidate, const string& s) {
138+
int count = s.size() / candidate.size();
139+
string temp;
140+
for (int i = 0; i < count; i++) {
141+
temp += candidate;
142+
}
143+
return temp == s;
144+
}
145+
};
146+
```
147+
148+
## C#
149+
150+
```csharp
151+
public class Solution
152+
{
153+
public string GcdOfStrings(string str1, string str2)
154+
{
155+
string result = "";
156+
int minSize = Math.Min(str1.Length, str2.Length);
157+
158+
for (int i = 1; i <= minSize; i++)
159+
{
160+
if (str1.Length % i == 0 && str2.Length % i == 0)
161+
{
162+
string candidate = str1.Substring(0, i);
163+
if (IsValid(candidate, str1) && IsValid(candidate, str2))
164+
{
165+
result = candidate;
166+
}
167+
}
168+
}
169+
170+
return result;
171+
}
172+
173+
private bool IsValid(string candidate, string s)
174+
{
175+
return string.Concat(Enumerable.Repeat(candidate, s.Length / candidate.Length)) == s;
176+
}
177+
}
178+
```
179+
180+
## JavaScript
181+
182+
```javascript
183+
var gcdOfStrings = function (str1, str2) {
184+
let result = "";
185+
const minSize = Math.min(str1.length, str2.length);
186+
187+
const isValid = (candidate, s) => {
188+
return candidate.repeat(s.length / candidate.length) === s;
189+
};
190+
191+
for (let i = 1; i <= minSize; i++) {
192+
if (str1.length % i === 0 && str2.length % i === 0) {
193+
const candidate = str1.substring(0, i);
194+
if (isValid(candidate, str1) && isValid(candidate, str2)) {
195+
result = candidate;
196+
}
197+
}
198+
}
199+
200+
return result;
201+
}
202+
203+
```
204+
205+
## Go
206+
207+
```go
208+
func gcdOfStrings(str1 string, str2 string) string {
209+
result := ""
210+
minSize := len(str1)
211+
if len(str2) < minSize {
212+
minSize = len(str2)
213+
}
214+
215+
for i := 1; i <= minSize; i++ {
216+
if len(str1) % i == 0 && len(str2) % i == 0 {
217+
candidate := str1[:i]
218+
if isValid(candidate, str1) && isValid(candidate, str2) {
219+
result = candidate
220+
}
221+
}
222+
}
223+
224+
return result
225+
}
226+
227+
func isValid(candidate, s string) bool {
228+
return strings.Repeat(candidate, len(s)/len(candidate)) == s
229+
}
230+
```
231+
232+
## Ruby
233+
234+
```ruby
235+
def gcd_of_strings(str1, str2)
236+
result = ""
237+
min_size = [ str1.size, str2.size ].min
238+
239+
(1..min_size).each do |i|
240+
next unless (str1.size % i).zero? && (str2.size % i).zero?
241+
242+
candidate = str1[0...i]
243+
next unless candidate * (str1.size / i) == str1
244+
next unless candidate * (str2.size / i) == str2
245+
246+
result = candidate
247+
end
248+
249+
result
250+
end
251+
```
252+
253+
## Other languages
254+
255+
```java
256+
// Welcome to create a PR to complete the code of this language, thanks!
257+
```
258+
259+
Dear LeetCoders! For a better LeetCode problem-solving experience, please visit website [LeetCodePython.com](https://leetcodepython.com): Dare to claim the best practices of LeetCode solutions! Will save you a lot of time!
260+
261+
Original link: [1071. Greatest Common Divisor of Strings - LeetCode Python/Java/C++/JS code](https://leetcodepython.com/en/leetcode/1071-greatest-common-divisor-of-strings).
262+
263+
GitHub repository: [f*ck-leetcode](https://github.com/fuck-leetcode/fuck-leetcode).
264+

0 commit comments

Comments
 (0)