Group anagrams | Leetcode #49
Вставка
- Опубліковано 27 вер 2024
- This video explains a very important interview problem which has already been asked in many big MNCs like microsoft,amazon,google,facebook etc. The problem says that given an array of strings, we need to group them such that strings in a group must be anagrams of each other. I have explained using 3 methods with code. It makes use of hashmap and hashmap of hashmap for optimal solution. CODE LINK is given below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.co...
Check if 2 strings are anagram: • Check if two strings a...
Those two words "eat" "bat" hurts differently now, if you know what i mean !!!
😂😂
😂😂
🤣🤣
😂😂
To all the people in the future, We are currently in the COVID-19 pandemic.
You can't explain more better than this, You deserve an award.
Thanks :)
Very easy to understand and detailed
The third approach can be further optimised by using integer as the hash key. As we have max 26 char, we can represent the hash as an integer. Iterate over the chars of the word and set the particular position bit in the integer and at the end use this integer as key/bucket in the map. Your map syntax would look something like this.
Map
you mean to say Map ???
I think this won't work. Can you try with "abc" and "cc" will come under the same bucket.
i dont think we can do this because the word can have duplicate characters, so this will fail. Like how do we differentiate the word "cat" is different from "caat"
Tons of thanks for such a precise explanation. No one can teach better than this. Hats off !!!!!
Thanks :)
@@techdose4u welcome
Sir 3rd method time Complexity will be approximatly equal to 2nd method as to implement 3rd method we will use map, as we cannot use unordered_map inside unordered_map
So time for third is Time - O(N * (M*log(N) + logN))
You can create your own hasher for map vector pair
exactly !! you cannot simplify it from 2nd one ,it becomes worse
one of the most underrated channels!
:)
can you share the code of the third most optimised approach without sorting ??
I cannot able to code it properly
Hi, Thanks for this video.. i was stuck with below input ["",""]. the expected outcome is [["",""]].
but in map since the empty string will be repeating the output im getting is [[""]]. i can handle for this edge case if string is empty, but pls advise if we can have better way.
Second approach is awesome, we can also solve this problem using trie data structure
👍
why do you sort the stri[i] instead of the temp string? why do you prefer to modify the input instead of a temporary variable?
I cannot believe this is a medium... graph problems I find are easier than this nonsense problem...
THIS VIDEO IS JUST WOW, THANK YOUUU SOOO MUCH, I WAS NOT ABLE TO UNDERSTAND THIS AFTER HOURS I FIND IT AND IT IS SUCH A RELIEF, THANKS TON!!!!
Welcome :)
Ridima send me the cpp optimal code.
We can sort the temp string and not the original string so that the original string does not change if we have this constraint
Yes correct.
how abt Xoring each letter of a word and then will xor the words itsself, when xor results in 0 then they are anagram
Great explanation, this video is best among all the other videos on UA-cam because there are no shortcuts in it, which makes it understandable very easily
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
strDic = {}
for s in strs:
arr = [0]*26
for i in s:
arr[ord(i)-97] += 1
# As arr is an array and we can not use an array as a key of dictionary so make arr a tuple
key = tuple(arr)
if key not in strDic:
strDic[key] = [s]
else:
strDic[key] += [s]
res = []
for key in strDic:
res.append(strDic[key])
return res
Amazing!!!! Never really needed to see the code. Just by understanding the thought process I can implement the code. Thank you Sur!!
Good evening lol!
😂 good evening :)
Please put the code of optimal approach in C++. I am not able to implement one map inside another map in C++.
The code in the video is java or c++;
One of the best explanation for this problem. Thank you sir
Very very very well explained brother! Thanks so much.
Welcome :)
can we take unordered_map
basically unordered_map, in place of map
if we add the ascii values of a word and use unordered_map it will be a single traversal and no need for sorting, correct me if I was wrong ;)
But many words can have same ascii values sum but different letters in it
Thank you bro!
Glad you are doing the April challenge!
Yes ;)
Amazing explanation with so much clarity. Thanks man.
Welcome:)
OK, send the cpp optimal code now.
if any charector comes twice like book then 3rd method will work ?
Nice explanation sir..........thanks for making video it was really helpful
unordered_map myMap;
unordered_map myMap;
these line show me error on leetcode
Great explanatio, thank you so much! I've subscribed!
really good explaination
Awesome explanation. ThankYou Mam🐵
It's sir 😂
video bahr se hi itni achhi lagi bina dekhe hi comment kr diya😅
Amazing explanation
you make life simple
Your videos are just awesome man!!!!
Thanks :)
thanks that was very clear and your diagram was very helpful to understand :)
awesome explaination!!!!!!! thanks a lot
Welcome :)
where the october challlenge playlist sir pls upload it
I will upload when I reach my workplace. Currently I am at home.
Nice explanation!! But I'm not able to code for the most optimal approach..... How to add data in map within map...I'm not getting that
for(int i=0;iint)
@@shiyadh4471 Thanks
bro your most optimal approach is taking more time than 2nd approach....
Don't remeber. I will see.
Can we use union find here?
sir plz solve the problems in python
Sir,can u make videos on recursion plzz sir
Sure I will :)
What will be space complexity of 2nd and 3rd method ??
In worst case,
Key part of map: O(NK) -all are unique strings
Value part : O(NK) -all N strings of K length
Thanks a lot ...
Can we take a sum of ASCII values and use them as "key" to hashmap?
Just thought about this idea before watching the video, definitely you can!
No, we can't. For, example, "ill" and "duh" have the same sum at the end.
i is equal to 105
l is equal to 108
l is equal to 108
321
d is equal to 100
u is equal to 117
h is equal to 104
321
thank you sir!
Thanku ❤️❤️❤️
biliblibilblibilbliblib
You are speaking like a robot in a monotonous tone please improve it .
Btw explanation is good .
sure
thanks
how come time complexity is o(n*k) when we are using orderedmap in the last optimal approach?
Sir, please provide the optimal solution in C++. Many of us are not able to implement that, please do that🙏
Sure
@@techdose4u Where have you posted that?
It’s not possible to use unordered map for the optimal solution because unordered map doesn’t have hasher for . So either you create your own hasher or use regular map
I was trying to solve this problem since yesterday night. But when I came to know about map, Its just a matter of a min to solve that one... Thank you TECH DOSE... God bless you...🙌🏻🙌🏻🙌🏻🙌🏻🙌🏻
Thanks :)
Your videos are of different level...thank you so much sir!
I solved the problem but I'm failing at time complexity can you help me out?
class Solution {
public:
vector groupAnagrams(vector& strs)
{
vector answers;
bool flag = false;
for (unsigned int i = 0; i < strs.size(); i++)
{
if (answers.size() == 0)
{
vector temp = { strs[i] };
answers.push_back(temp);
}
else
{
flag = false;
unsigned int j;
for (j = 0; j < answers.size(); j++)
{
if (IsAnagram(answers[j][0],strs[i]))
{
flag = true;
break;
}
}
if (flag)
answers[j].push_back(strs[i]);
else
{
vector temp = { strs[i] };
answers.push_back(temp);
}
}
}
return answers;
}
bool IsAnagram(string a, string b)
{
int const maxChar = 26;
int count[maxChar] = { 0 };
if (a.length() == b.length())
{
for (unsigned int i = 0; i < a.length(); i++)
{
count[a[i] - 'a']++;
count[b[i] - 'a']--;
}
for (unsigned int i = 0; i < maxChar; i++)
{
if (count[i] > 0)
return false;
}
return true;
}
return false;
}
};
In 2nd approach , I used a map< vector, vector > , It gave an error. If anyone knows, please comment a simple explanation
How to loop over within a single string in the vector of strings, to store their character frequency in the hashmap ? As we don't have another iterator to go through each character within a selected string
Thanks Surya for the amazing explanation! :)
Just a quick question, do we need to write Sorting algo in a coding interview? Or we can use just write Sort (which is taken care by the framework itself). I'm asking this because we've limited time and sorting is not the main focus here.
No need to sort. If they ask them do otherwise not required.
Bhul jane ka hunar....mujhko sikhate jao......
Jaa rahe ho ..toh sabhi ashk mitaate jaao.....
Thank you so much sir!!! I could code it by just watching 5 minutes of your video! Thanks a lot for explaining things in such a simplified way :) Keep growing!
Thanks 🙂
2nd approach
class Solution {
public:
vector groupAnagrams(vector& strs) {
vector ans;
map mp;
int n = strs.size();
string temp;
for(int i=0;isecond);
}
return ans;
}
};
you are welcome !
Please share optimal code in c++
Sure
bhaiya is geeks for geeks sufficient for competitive programming
Geeksforgeeks is sufficient for placements but for competitive programming, you will have to keep participating in contests. Geeks will provide materials but participation will help you improve you weak areas. So participate in codechef or codeforces.
U are doing great job bhaiya♥️
Love from Jharkhand
Thanks :)
I don't think we will be able to use unordered map in second approach. ordered_map operations will cost log(n)....increasing the time complexity to mnlog(n)
very big Thanks for this video
Welcome :)
Mind blowing
Thanks :)
great solution man!
Thanks :)
why it isn't working with unordered map?
what a solution! 🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥
Thanks for making this one
Kindly check the time compexity:
vector groupAnagrams(vector& strs) {
int n = strs.size();
map ump;
for(int i =0;i < n; i++)
{
string s = strs[i];
vector hsh(26,0);
for(int j = 0; j < s.length(); j++)
{
hsh[s[j]-'a']++;
}
ump[hsh].push_back(s);
}
vector ans;
for(auto it: ump)
{
auto temp = it.second;
ans.push_back(temp);
}
return ans;
}
O(100n)