Thanks bhai. Below is the Java code: class Solution { public boolean isConcatenated(String word, Set st, Map map) { if(map.containsKey(word)) return map.get(word); int l = word.length(); for(int i = 0 ; i String prefix = word.substring(0, i+1); String suffix = word.substring(i+1, l); if((st.contains(prefix) && st.contains(suffix)) || (st.contains(prefix) && isConcatenated(suffix, st, map))){ map.put(word, true); return true; } } map.put(word, false); return false; } public List findAllConcatenatedWordsInADict(String[] words) { int n = words.length; Set st = new HashSet(); Map map = new HashMap(); for(String s : words) st.add(s); List result = new ArrayList(); for(int i = 0 ; i String word = words[i]; if(isConcatenated(word, st, map)){ result.add(word); } } return result; } }

@souravjoshi2293

Жыл бұрын

Thanks man

@thevagabond85yt

5 ай бұрын

cache was the key otherwise 42/43 test case passed.

Because of you I have started learning DSA! 🛐❤

nice solution thanks brother

Whaaat 😅 This seriously became extremely Easy. That's your magic bro

Amazing solution bro... you literally made it super easy

great explanation thanks keep the good work 🙏

Amazing explanation 👏👌

you are the reason I started coding again

If anyone has a BruteForceSolution then please 🙏 comment here...

Amazing explanation

from the last few days i have been following your videos, how you make these intuitions so easily where as i struggle a lot.

@codestorywithMIK

Жыл бұрын

Thank you so much ❤️ I always suggest people to solve atleast 1 qn a day and see other people’s approaches also to learn more.

Thanks for this soln !!😇

Nice 👌🏻

great explained

Bhai yrr jldi video daala kro subhe se itni sari video dekh li kisi ki smjh ni aayi pta n kya he approach bta rhe the apki video dekhte he sb smjh aane lga bs apki video ka he wait rheta h ab❤✔

@codestorywithMIK

Жыл бұрын

Thanks a lot Nitesh. Actually i take some time to think on how to explain it in easiest way possible, also have to manage office . Sometimes delayed 😅 Thank you so much for watching my videos Nitesh

@souravjoshi2293

Жыл бұрын

True man. Ye video dekhne me sab ek baar me clear hoagy

@niteshk0487

Жыл бұрын

@@codestorywithMIK i can understand hmme bhi apni trha bna do like jis level tak app sochte ho 😅

@codestorywithMIK

Жыл бұрын

Soon we all will rock 😊 Keep practising with me

🔥

Thanks a lot once again bhaiya for making this ques easy. Just curious to know your thought process while solving a problem. Once again thank you❤

@codestorywithMIK

Жыл бұрын

Thanks a lot Arjun. Actually i try to spend around 30-40 minutes (sometimes more than what i take to solve a problem), just to come up with words I should use to make me explanation easy. 😅 I realised, it’s not tough to solve problems, but the toughest part is to explain it to someone in easy words With solving more and more problems with different approaches, these naturally start coming to you.

First comment!!!😁

Do "LC : 139 Word Break" before solving this problem.

Please cover Leetcode question no 30 Substring with Concatenation of All Words

Bro wait a sec, ye itna easy kaise ho skta 😂 btw great explanation ❤

I think complexity will be o(n*l^2) as due to memoization , loop as well as substring function will be skipped

Ye kiya explanantion tha damn bhiaya.. you rock❤‍🔥.. Thank you so much.. and how is your health now?😇

@codestorywithMIK

Жыл бұрын

I am feeling better. Thank you 😊

Finally exams over, back to your channel

@mohitrathore8808

Жыл бұрын

I thought exact same optimal solution but unable to write code for it, Brute to dimag me aaya hi nhi lol...

As said .. I coded alone after watching intuition Well, ek baath bhai dil se - Tum bharosa dila dete ho kheke - easy hai question aur solution.. wohi sunke aacha lagta hai Warna saachi kahu toh fati padi hi rheti hai 😛 sabh kudh jaate solution par recursion leke aur ghanta thikke se samjhta nahi kuch 😀

@codestorywithMIK

Жыл бұрын

Means a lot ❤️😊

Your explanation is amazing bro... I want to know do you write using mouse or tablet &stylus ?

@codestorywithMIK

Жыл бұрын

Thank you Ashutosh ❤️ Tab and stylus 🙂

the brute force approach that u have shown above in not correct because repeatition of words is allowed here, For Example if I have taken "cat" once I cant take it again as the iterator is shifted forward. Tell me If i am wrong.

@codestorywithMIK

Жыл бұрын

I think you are right Yash. Thanks for pointing that out. I will explore more on that approach. Makes me wonder unbounded knapsack 🤔🤔🤔

@humanity7880

2 ай бұрын

yes I was searching for someone to point this out

are these solvable at first attempt ? or learn the techniques from videos and revisiing is fine ?

@codestorywithMIK

Жыл бұрын

Hi Vishal, It’s TOTALLY fine if these are not solvable at once. It’s TOTALLY fine to revise or practice it later after understanding it from the video. What’s important is that, you understand the solution (never memorize it). I had solved similar problems before, that’s why i could come up with this I am 100% sure; if you solve more and more, you will also be able to solve later. Don’t worry

@souravjoshi2293

Жыл бұрын

same Qn

question number 30 of leetcode solution

Java Code Using Java HashSet class Solution { Set set = new HashSet(); public List findAllConcatenatedWordsInADict(String[] words) { List result = new LinkedList(); for(String s: words){ set.add(s); } for(int i=0; i

@rbrt8

Жыл бұрын

Some edits, need to your code, i mean, in JAVA, substring written like that "substring" not "subString". btw thanks for the code using Hashset

@recessionriche

Жыл бұрын

@@rbrt8 yep thanks fixed it, had a typo xP

in my code i just passed the word by reference and it gave me tle after that i removed it and it got submitted . passing by value takes more time by creating a copy than passing by reference then why did i get tle

First really thanks bhaiya Second what I thought about this question is I will traverse in words array and by picking each word I will check that is it forming by concatenation by remaining words and if true then we will push it to the ans else will move to other word but can you help me bhaiya how to check that if a word is concatenation of remaining words I am not able to handle the remaining part here And about time complexity it can be understood as we are iterating over the words array so it will be O(n) and in isConcatenated we are traversing over word of length l so O(l) Second Inside the loop we are finding substring so another O(l) and also for suffix we are again calling the isConcatenated we are again traversing the whole word of length l so O(l) again Final time complexity would be O(n*l^3) if there is anything wrong in the explanation of time complexity so please please correct me bhaiya Third thing bhaiya can't there be a case where prefix is forming by concatenation and suffix is present in the set

@codestorywithMIK

Жыл бұрын

What you explained in the first part of your comment - That’s actually brute force where you will have to try every possible combination to see if that’s a concatenation of other words. Also about the prefix thing you said, We are actually trying every prefix starting from length = 1 and then length = 2 and so on, and we are checking for presence of prefix also in the set, so that also covers the prefix case. You can try with any example which is small for easy dry run

@udaytewary3809

Жыл бұрын

@@codestorywithMIK yes bhaiya the time complexity is before memoization as I don't know about dp so I didn't explain the time complexity after that

bhaiya..hum prefix bhi toh check kar sakte hai...magar hum nhi kar rahe hai. For example: ["do", "g", "cat", "dogcat"] Issme kaise karenge?

@codestorywithMIK

Жыл бұрын

In this example : when we iterate “dogcat”, We will find prefix “do” in our set. Then further we will check “gcat” recursively Which again will break it in “g” And “cat” which is a valid case as both are present in set. Hence it works in this case too

@pranavkhatri30

Жыл бұрын

@@codestorywithMIK Thanks a lot Bhaiya!

Hi Bhaiya , Can you please make a video on this "473. Matchsticks to Square". I am having difficulty while solving this.

@codestorywithMIK

Жыл бұрын

Sure . Added to my list Soon

@turing_machine544

Жыл бұрын

@@codestorywithMIK Thanks Bhaiya

Someone post the brute force code

PLease explain ho to improve Time Limit Exceeded : class Solution { public static boolean isConcatenated(String word,HashSet set){ int l = word.length(); for(int i = 0;i

Bhaiya instead of making a DP can't we just add the suffix in the set if isConcatenated(suffix,st)) is true if((st.find(prefix) !=st.end() && isConcatenated(suffix,st)) || (st.find(prefix) !=st.end() && st.find(suffix)!=st.end())) { st.find(suffix); return true; } Please reply

@codestorywithMIK

Жыл бұрын

But when you find the result in the end, you will take then out from your set which also contains unconcatenated words which will lead to wrong answers. It’s better to make this change and see how it goes. st.insert(suffix)

@adambadam6703

Жыл бұрын

It is passing all the test cases and the running time that is shown on Leetcode is 250ms. For the DP solution we are applying it on the word , which the unorderedset is already doing. We should apply dp on the suffix. I think best is to just add the suffix in the set if conditions are met and we don't need DP here. Please share your views as well Thankyou :)

@codestorywithMIK

Жыл бұрын

Wowieee. That’s an amazing observation I got your point now. Thanks a lot Adam for your precious input ❤️

@adambadam6703

Жыл бұрын

@@codestorywithMIK Always your biggest fan.Keep up the good work ♥️♥️

Bro do not stop making videos..

@codestorywithMIK

Жыл бұрын

Thanks Hrishikesh. I will be just on 3 weeks break in February because of travelling out of India. But it’s a promise, i will be back with more contents. Thank you for trusting my channel

@manishv.8167

Жыл бұрын

@@codestorywithMIK Please meanwhile the vacation atleast upload videos of graph concept if possible

@codestorywithMIK

Жыл бұрын

Actually it’s not a vacation. Some medical emergency. However , i will try to put Graph videos and will come soon.

959. Regions Cut By Slashes Please make video on it.

@codestorywithMIK

Жыл бұрын

Noted to my list. Soon

Could please explain how to do it with trie?

@codestorywithMIK

Жыл бұрын

I will add this Qn in my trie playlist too. Thanks for asking Amandeep

please provide bruteforce sol code

sir ek doubt hai, in wrost case N would be 10^4 and L would be 30 and apna time complexity hai O( n * l ^4) so it will be 10^4 * 30 ^ 4 which should give time exceed but fir bhi code chal rha hai, i am confused 😥😕

@codestorywithMIK

Жыл бұрын

That depends on what Leetcode has set as TLE and also what test cases they are testing our solution with

@sanjaykatta6499

8 ай бұрын

I got TLE without memoization. I used java for coding.

st.find(prefix)!=st.end(), iska mtlb present hai set mei, how? thoda explain kr do pls

@codestorywithMIK

Жыл бұрын

The find() returns an iterator to the element which is searched in the set. If the element is not found, then the iterator points to the position just after the last element in the set (which is the end of the set .i.e st.end())

@AbhijeetKumarAJ

Жыл бұрын

@@codestorywithMIK thank you soo much

#include #define value 1+2 using namespace std; int main() { printf("%d and %d ", value/value, value*3); return 0; } Can you please explain why its output is 5 and 7. I am not getting it.🙏

@twi4458

Жыл бұрын

in #define we just put expression as it is. so for in this example : 1st %d will be: 1 +2/1 + 2 and 2nd %d will be: 1+ 2*3

@anubhavsingla3126

Жыл бұрын

Thanks brother

why my CODE is giving TLE: .size() has a TC of O(1). So that is for sure its not a issue of .size(). vector res; unordered_map dp; bool isConcatinated(unordered_set s, string str) { if (dp.find(str) != dp.end()) return dp[str]; for (int i = 0; i { string pre = str.substr(0, i + 1); string suff = str.substr(i + 1); if ((s.find(pre) != s.end() && s.find(suff) != s.end()) || (s.find(pre) != s.end() && isConcatinated(s, suff))) { return dp[str] = true; } } return dp[str] = false; } vector findAllConcatenatedWordsInADict(vector &words) { unordered_set s(begin(words), end(words)); for (auto e : words) if (isConcatinated(s, e)) { res.push_back(e); } return res; }

@codestorywithMIK

Жыл бұрын

Pass the unordered set s by reference

@twi4458

Жыл бұрын

@@codestorywithMIK Why that makes difference. I have seen people codes that used to pass containers as reference. Its not necessary but why important?

@codestorywithMIK

Жыл бұрын

Very important. I have answered this in many other comments. Passing by value creates extra copy of variables , everytime you call the function. Passing by reference helps to avoid the copy operation and saves time

@codestorywithMIK

Жыл бұрын

Read this : www.geeksforgeeks.org/difference-between-call-by-value-and-call-by-reference/amp/

@twi4458

Жыл бұрын

@@codestorywithMIK Thankyou sir got it. 🤗

Superb explanation bhaiaya , as u said I coded it myself , and u made it absolutely easy my code : bool isConcatenated(string word, unordered_set &st, unordered_map &memo){ int n = word.size(); //lookup if (memo.find(word) != memo.end()){ return memo[word]; } for (int i=0 ; ii string suffix = word.substr(i+1); //i+1 -> n-1 //then check 2 conditions if ((st.find(prefix) != st.end() and st.find(suffix) != st.end()) or (st.find(prefix) != st.end() and isConcatenated(suffix, st, memo))){ return memo[word] = true; } } return memo[word] = false; } vector findAllConcatenatedWordsInADict(vector& words) { vector ans; unordered_set st(words.begin(), words.end()); //for memoization unordered_map memo; for (auto word : words){ if (isConcatenated(word, st, memo)){ ans.push_back(word); } } return ans; }

I think time complexity analysis is not correct, the isconcatenated can call itself som number of times not two times,

@codestorywithMIK

8 ай бұрын

Hey, thank you so much raising the Qn. Let me have a look at this again. 🙏😇