Greatest Common Divisor of Strings - Leetcode 1071 - Python
🚀 neetcode.io/ - A better way to prepare for Coding Interviews
Solving Greatest Common Divisor of Strings Leetcode 1071, today's daily leetcode problem on January 31st.
🥷 Discord: / discord
🐦 Twitter: / neetcode1
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
Problem Link: leetcode.com/problems/greates...
0:00 - Read the problem
1:10 - Drawing Explanation
5:32 - Coding Explanation
leetcode 1071
#neetcode #leetcode #python
Пікірлер: 45
I was stuck on this problem and it literally took me the first 3 minutes to understand where I'm blocked, paused the video and successfully solved it 🥳
I had asked for more easy problems and here you are. Thank you.
@NeetCodeIO
Жыл бұрын
Well normally I just do the daily LC problems, so difficulty is usually out of my control 😅
Maybe it’s just late but I feel like I’ve seen easier mediums than this
@NeetCodeIO
Жыл бұрын
Yeah, this is definitely difficult for an easy
there is an insane solution that involves knowing that there is a GCD of strings if str1 + str2 == str2 + str1
@zeta_meow_meow
Жыл бұрын
damn bro , discuss section is surely amazing
@axelstahl4386
Жыл бұрын
It’s because they all have to be made up of the same stuff. Like aa + a=a+aa cause it’s just a repeated. But b + a != a + b because it’s not one thing repeated, or a factor
@sheeniebeanie2597
Жыл бұрын
class Solution: def gcdOfStrings(self, str1: str, str2: str) -> str: if str1 + str2 == str2 + str1: x = gcd(len(str1),len(str2)) return str1[:x] else: return ""
@zaidnissar356
7 ай бұрын
Holy frick that is an insane solution. My mind is blown!!
@iameenr
4 ай бұрын
@@sheeniebeanie2597Phenomal 😮 How can one come up with such ideas!
That modulo operation to rule out the substring sizing is such a good pointer for optimizing the solution
This video helped explain it so well glad i watched
Keep uploading more leetcode problems as well as system design.
divmod() is a nice method for your isDivisor() function. It returns both the integer division result and the remainder as a tuple. divmod(5, 2) = (2, 1)
Awesome quality content
How is this easy. I'm starting leetcode and the first 2 so far was a bit hard
how about if we use ascii to find the gcd?
Thank u!
Correct me if I'm wrong, but in line 9, minute 8:39 it does not work in bot cases as you described. Behind the "and" (str1[:l] * f1 == str1 and str2[:l] * f2 == str2) we need to compare str2 to the multiple of str1 because otherwise it is not checked if the actual letters of the substring are the same in str1 and str2. So this is the correct way to do it: str1[:l] * f1 == str1 and str1[:l] * f2 == str2
@mnaresh3382
5 ай бұрын
I was about to say that too.
I found this solution that works, unlike the solution in this video (which doesn't seem to solve all test cases on my end): class Solution(object): def gcdOfStrings(self, str1, str2): if str1 + str2 != str2 + str1: return "" def gcd(a, b): while b: a, b = b, a % b return a return str1[:gcd(len(str1), len(str2))]
@kingkidc2844
7 күн бұрын
The solution in this video isn't right for all cases return str1[:l] * p == str1 and str2[:l] * q == str2 this code should be switched to return str1[:l] * p == str1 and str1[:l] * q == str2 so it compares the substring str1 with str2
im confused on the big o explaination could someone explain it? i would have thought itd just be m cause isDivisor is just refactored out of the main loop its not like a smaller loop right.
i thought of this approach was thinking why no one did this instead of str1+str2 ,like every soln has that code only idk why?
this isn't easy, I used recursion. But thank you for the explanation just so I can see how others solve it. I know eventually this will be easier for me.
lol this is more on the medium side
🔥🔥🔥
There is a linear solution, based on the fact that str1 and str2 have a GCD string if and only if str1 + str2 == str2 + str1. But I fail to find a solution that explains why the right-to-left direction is true.
@sheeniebeanie2597
Жыл бұрын
i made the linear solution--it worked in leetcode but dk if it works generally
wow, nice
not that easy i guess 😅
I think I have to watch it again... I got lost .
Neetcode and NeetcodeIO are two different account?
An easier solution: def gcdOfStrings( str1, str2): if str1 + str2 != str2 + str1: return "" # initializa the maximum possible length of the GCD max_length = min(len(str1), len(str2)) for length in range(max_length, 0, -1): if len(str1) % length == 0 and len(str2) % length == 0: return str1[:length] return ""
This code only passes 21 out of 123 test cases on leetcode
This should be a medium bruh
Time Complexity of below soln: O(logn)
Please correct the code as it would fail for str1 = 'ABCD' str2 = 'DEFH' the correction in line 9 should be as below return str1[:l]*f1 == str1 and str2[:l]*f2 == str2 and str1[:l] == str2[:l]
@hi-io
7 ай бұрын
It seems to me that it might not always work out, because str1 and str2 do not always follow the same order
@effortlessjapanese123
2 ай бұрын
hey can you explain why we need to add str1[:l] == str2[:l]?
How is this easy at the first place..naaaa
Bro, there is a more efficient solution that takes 2 lines of code in c++. Suppose the first string is s and the second is t then: string gcdOfStrings(string s, string t) { if(s+t != t+s) return ""; return s.substr(0, __gcd((int)s.size(), (int)t.size())); }
4:14 Man, what am I even looking at? It's not even psuedo math that makes any sense whatsoever. If you had put something like 6 = 2x, it's basic algebra sure. But wow, that is an awful explanation in comparison, and I would suggest maybe redoing this video's section to be more clear. The problem itself is the worst word salad I have ever read in my entire life, but this solution is even more convoluted.