Concatenated Words - Leetcode 472 - Python

[@aditya-lr2in]

I opened your yt video, saw first 5 seconds and went to code, came back after 12 mins solving it, and skipped to end to see ur code, and lmao its almost the same, even with the naming like wordset and me commenting the size of cache (30 * N * 30), thanks for the teachings !

[@phoenix_1_3]

Watched your explanation part and I went to code. First I got wrong op since I was not using a set, then after using a set, the solution got accepted. Man, you made the problem so simple for even noobs like me. You are really a legend ❤‍🔥

[@EscapeThirty]

APPROACH 1 IS INCORRECT AS A WORD CAN BE PRESENT MUTIPLE TIMES AND 2^N POSSIBILTIES CONSIDER ONLY ONE OCCURENCE OF IT THAT TOO IN ORDERED WAY

[@NeetCodeIO]

I think there are no duplicates in the input if that's what you meant. But yes, some of the concatenations would be individual words and we would definitely have to filter them.

[@rowanus116]

@@NeetCodeIO I've had a hard time filtering those individual words who is not a concatenation, How could we filter those words? Thanks

[@Avighna]

They recently made this harder. Immediately thought of the brute force, but it's now n

[@PedanticAnswerSeeker]

class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: def is_concatenated(word, word_set, memo): if word in memo: return memo[word] n = len(word) for i in range(1, n): prefix = word[:i] suffix = word[i:] if prefix in word_set and (suffix in word_set or is_concatenated(suffix, word_set, memo)): memo[word] = True return True memo[word] = False return False word_set = set(words) concatenated_words = [] memo = {} for word in words: if is_concatenated(word, word_set, memo): concatenated_words.append(word) word_set.add(word) return concatenated_words this code worked for me, so i don't think they made it different

[@CostaKazistov]

Amazing how simple this solution is.

[@SafalGautam-jp7ew]

first approach of brute force might be incorrect because we do not know that whether or not the string combinations that we will make are single or concatenated. for example -> input: a, ab, cd combinations would be [aabcd, aab, acd , a, abcd, ab, cd] here we have a as well how can you say that whether "a" here is concatenated or not. so, brute forcing finding every possible solutions wouldn't make any sense

[@geyushen4369]

Hard is definitely a misleading label for this question. Thought my half-brute-forcy solution was a TLE for sure, but it worked and almost the same as the official solution lol

[@anu1097]

Time limit exceeds for 1 case. Why not use trie ?

[@abrahamm1145]

Nice video! Im having trouble visualizing why the time complexity would be N *L^3 instead of N * L^4 when memoizing though. Does anyone have an example with a word/words that could showcase that?

[@Cccccccccc7850]

u shattered my confidence at the beginning lol

[@satyajeetdas6577]

We can also use Trie Data Structure for this solution which is almost very similar # CODE-1 #we can optimise by not creating trie for all and create if check func returns False. class Trie: def __init__(self): self.list=[None]*26 self.flag=False def containsKey(self,chr): if self.list[ord(chr)-ord('a')]!=None: return True return False def addkey(self,chr,node): self.list[ord(chr)-ord('a')]=node def getkey(self,chr): return self.list[ord(chr)-ord('a')] def setflag(self): self.flag=True def getflag(self): return self.flag class Solution: def findAllConcatenatedWordsInADict(self, words: List[str]) -> List[str]: self.node=Trie() for word in words: node=self.node for w in word: if not node.containsKey(w): node.addkey(w,Trie()) node=node.getkey(w) node.setflag() def check(ind,node,word,count): curr=node for i in range(ind,len(word)): if not curr.containsKey(word[i]): return False curr=curr.getkey(word[i]) if curr.getflag() and check(i+1,node,word,count+1): return True if count>=1 and curr.getflag(): return True else: return False res=[] for word in words: if check(0,self.node,word,0): res.append(word) return res

[@satisfyingwalks4010]

Hi, could you please make a solution video to LC 801 - "Minimum swaps to make sequences increasing" , I can't find a satisfactory video solution to that on yt

[@MP-ny3ep]

Thanks a ton ! Phenomenal explanation as always.

[@iamnoob7593]

Thanks neetcode

[@krateskim4169]

Awesome explanation

[@Kilvny]

Thank you so much very informative!!!

[@mohithadiyal6083]

Amazing explanation 👍

[@AMX0013]

Got a variation of this for Amazon phone screen. Yes I had to analyse the TC and SC. And It was modified and had to return the the compound word, and the list of combination of concatenations that would yield it. I came close, but didn't make it

[@Gabagool22]

i just had the same question in an Amazon phone screen, did you pass? Kind of a pretty difficult one in my opinion.

[@AMX0013]

@Gabagool22 i didnt pull through. I couldnt get started but after i got to the prefix and suffix idea i think i took it along smoothly tho

[@Gabagool22]

@@AMX0013 Good luck on the next one! How many days after did they provide feedback? I am still waiting for a response.

[@AMX0013]

@Gabagool22 i got the rejection the next day itself. My friend mentioned it takes 1day for OA results 3days for phone screen results 5 days for loop results

[@jessanraj9086]

Wow that's an amazing explanation

[@NeetCodeIO]

Glad it was helpful!

[@DipakKawale]

class Solution { Set set; public List findAllConcatenatedWordsInADict(String[] words) { this.set =new HashSet(Arrays.asList(words)); List list = new ArrayList(); for(String word:words){ if(dfs(word)){ list.add(word); } } return list; } public boolean dfs(String word){ for(int i=1;i

[@Tom910ru]

I think prefix tree can be good for this task

[@tanishgotti3659]

Bro you didn't explain the TC rigorously.

[@user-le6ts6ci7h]

I don't think the time complexity is right

[@DevvOscar]

What do you use to draw?

[@NeetCodeIO]

Paint3d, but I'm thinking about switching to excalidraw

[@NoName-lq7xk]

best 🔥🔥

[@aadil4236]

Actually, without caching it won't pass. I tried it with js and python3.

[@rashzh5502]

Nice!

[@lakshmanvengadesan9096]

*If you are preparing for coding interviews* yes that's true, but most of the big tech companies have freezed their hirings

[@CostaKazistov]

A leetcode a day keeps unemployment away

[@jasonahn8658]

@@CostaKazistov THIS

[@HabibLawal]

This no longer works unfortunately

[@mahmudaliza4079]

@NeetCodeIO I think the brute force solution does not work. Iiuc, below is an example case with words has [cat, cats, dog, dogcat]. Can't upload screenshot. Please copy paste to some ide for better visual. The leaf has dogcat but it does not prove dogcat is a concatation of two other words dog and cat. Because cat came before dog, and we are only appending the next word, there is no combination that has dog first, then cat. And we are not considering adding same word twice i.e. catcat. Unless I am missing something. But based on video explanation, this approach does not look correct. Please update the video or comment with your feedback. Thank you. "" / \ cat: cat "" / \ / \ cats: catcats cat cats "" / \ / \ / \ / \ dog: catcatsdog catcats catdog cat catsdog cats dog "" / \ / \ / \ / \ / \ / \ / \ /\ dogcat: catcatsdogdogcat catcatsdog catcatsdogcat catcats catdogdogcat catdog catdogcat cat catsdogdogcat catsdog catsdogcat cats dogdogcat dog dogcat ""