Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitc5433a1

Browse files
committed
Update all solutions' changes in 2025-05-09.
1 parent5822928 commitc5433a1

6 files changed

+1396
-0
lines changed
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+
classSolution:
70+
defgcdOfStrings(self,str1:str,str2:str) ->str:
71+
result=""
72+
min_size=min(len(str1),len(str2))
73+
74+
for iinrange(1, min_size+1):
75+
iflen(str1)% i==0andlen(str2)% i==0:
76+
candidate= str1[:i]
77+
78+
if candidate* (len(str1)// i)== str1and candidate* (len(str2)// i)== str2:
79+
result= candidate
80+
81+
return result
82+
```
83+
84+
##Java
85+
86+
```java
87+
classSolution {
88+
publicStringgcdOfStrings(Stringstr1,Stringstr2) {
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+
privatebooleanisValid(Stringcandidate,Strings) {
105+
int count= s.length()/ candidate.length();
106+
StringBuilder sb=newStringBuilder();
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+
classSolution {
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+
boolisValid(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+
vargcdOfStrings=function (str1,str2) {
184+
let result="";
185+
constminSize=Math.min(str1.length,str2.length);
186+
187+
constisValid= (candidate,s)=> {
188+
returncandidate.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+
constcandidate=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+
funcgcdOfStrings(str1string,str2string)string {
209+
result:=""
210+
minSize:=len(str1)
211+
iflen(str2) < minSize {
212+
minSize =len(str2)
213+
}
214+
215+
fori:=1; i <= minSize; i++ {
216+
iflen(str1) % i ==0 &&len(str2) % i ==0 {
217+
candidate:= str1[:i]
218+
ifisValid(candidate, str1) &&isValid(candidate, str2) {
219+
result = candidate
220+
}
221+
}
222+
}
223+
224+
return result
225+
}
226+
227+
funcisValid(candidate,sstring)bool {
228+
return strings.Repeat(candidate,len(s)/len(candidate)) == s
229+
}
230+
```
231+
232+
##Ruby
233+
234+
```ruby
235+
defgcd_of_strings(str1,str2)
236+
result=""
237+
min_size= [ str1.size, str2.size ].min
238+
239+
(1..min_size).eachdo |i|
240+
nextunless (str1.size% i).zero?&& (str2.size% i).zero?
241+
242+
candidate= str1[0...i]
243+
nextunless candidate* (str1.size/ i)== str1
244+
nextunless 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)
[8]ページ先頭
©2009-2025 Movatter.jp