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 !
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 ❤🔥
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.
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
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
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
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
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?
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
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
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 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
@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 ""
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 !
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 ❤🔥
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
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.
@@NeetCodeIO I've had a hard time filtering those individual words who is not a concatenation, How could we filter those words? Thanks
They recently made this harder. Immediately thought of the brute force, but it's now n
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
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
Amazing how simple this solution is.
u shattered my confidence at the beginning lol
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
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
Time limit exceeds for 1 case. Why not use trie ?
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?
Thanks a ton ! Phenomenal explanation as always.
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
Thanks neetcode
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
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
i just had the same question in an Amazon phone screen, did you pass? Kind of a pretty difficult one in my opinion.
@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
@@AMX0013 Good luck on the next one! How many days after did they provide feedback? I am still waiting for a response.
@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
Awesome explanation
Amazing explanation 👍
Thank you so much very informative!!!
Wow that's an amazing explanation
Glad it was helpful!
What do you use to draw?
Paint3d, but I'm thinking about switching to excalidraw
I think prefix tree can be good for this task
Bro you didn't explain the TC rigorously.
I don't think the time complexity is right
best 🔥🔥
Nice!
Actually, without caching it won't pass. I tried it with js and python3.
*If you are preparing for coding interviews* yes that's true, but most of the big tech companies have freezed their hirings
A leetcode a day keeps unemployment away
@@CostaKazistov THIS
@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 ""
This no longer works unfortunately