They recently made this harder. Immediately thought of the brute force, but it's now n
@PedanticAnswerSeeker
4 ай бұрын
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
@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?
@tanishgotti3659
29 күн бұрын
Bro you didn't explain the TC rigorously.
@anu1097
Жыл бұрын
Time limit exceeds for 1 case. Why not use trie ?
@CostaKazistov
Жыл бұрын
Amazing how simple this solution is.
@MP-ny3ep
Жыл бұрын
Thanks a ton ! Phenomenal explanation as always.
@user-le6ts6ci7h
11 ай бұрын
I don't think the time complexity is right
@jessanraj9086
Жыл бұрын
Wow that's an amazing explanation
@NeetCodeIO
Жыл бұрын
Glad it was helpful!
@aadil4236
8 ай бұрын
Actually, without caching it won't pass. I tried it with js and python3.
@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
@DevvOscar
Жыл бұрын
What do you use to draw?
@NeetCodeIO
Жыл бұрын
Paint3d, but I'm thinking about switching to excalidraw
@rashzh5502
Жыл бұрын
Nice!
@mahmudaliza4079
2 ай бұрын
@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 ""
@HabibLawal
Жыл бұрын
This no longer works unfortunately
@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
@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
4 ай бұрын
@@NeetCodeIO I've had a hard time filtering those individual words who is not a concatenation, How could we filter those words? Thanks
@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
@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
@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
@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
@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 ❤🔥
@iamnoob7593
Ай бұрын
Thanks neetcode
@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 !
@Cccccccccc7850
11 ай бұрын
u shattered my confidence at the beginning lol
@AMX0013
4 ай бұрын
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
4 ай бұрын
i just had the same question in an Amazon phone screen, did you pass? Kind of a pretty difficult one in my opinion.
@AMX0013
4 ай бұрын
@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
4 ай бұрын
@@AMX0013 Good luck on the next one! How many days after did they provide feedback? I am still waiting for a response.
@AMX0013
4 ай бұрын
@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
@Tom910ru
Жыл бұрын
I think prefix tree can be good for this task
@alqam2011
Жыл бұрын
Thank you so much very informative!!!
@buttofthejoke
8 ай бұрын
They added new test case. This problem is now giving TLE (Time Limit Exceeded). I used your trick *wordSet.has(prefix) && wordSet.has(suffix))* to get the solution. var findAllConcatenatedWordsInADict = function(words) { const wordSet = new Set(words); const map = new Map(); const isConcat = (word) => { if (map.has(word)) return map.get(word); for (let i = 1; i
Пікірлер: 43