class Solution: def longestStrChain(self, words: List[str]) -> int: from collections import defaultdict # cache len of chain cache = defaultdict(int) # word: length of chain # initiate data data = sorted(words, key=lambda w: len(w)) for word in data: # from word, the len of chain is 1 at 1st cache[word] = 1 for index in range(len(word)): # construct predecessor predecessor = word[:index] + word[index + 1:] if predecessor in cache: cache[word] = max(cache[word], cache[predecessor] + 1) return max(cache.values())
I don't know what to do , I was not able to think this straight even when I used hint from leetcode , But when I see some part of your solution , I was able to code it my self . I don't know where I am lagging , still not able to do many medium problems
does sorting even help us for this implementation? For the non recursive dp it helps, but for the recursive version it doesn't help since we go thru all the words anyway. can someone confirm this for me cuz im not sure lol.
from collections import defaultdict from typing import List class Solution: def longestStrChain(self, words: List[str]) -> int: words.sort(key=len) # Sort the words by length to process shorter words first word_chain = defaultdict(int) # Store the longest chain for each word for word in words: for i in range(len(word)): prev_word = word[:i] + word[i+1:] word_chain[word] = max(word_chain[word], word_chain[prev_word] + 1) return max(word_chain.values())
i know the company in the thumbnail might not matter to you much, but TikTok has actually asked this problem more frequently (according to Leetcode stats) than any other company. So idk why Meta's logo is in the thumbnail when they've asked it very infrequently in comparison
Love this explanation. Thanks man. One question, I have been following the 150 Qs from neetcode and then the leetcode 150 most asked. I started Trees yesterday. Is it possible to finish up the list within a month and understand everything? (Given, I have done every topic sequentially and Continuously review 3-4 of them each day) I am really worried about my upcoming interviews. And I find the important ones(Tree, Graph, DP) quite hard😅
yoo appreciate the daily upload, will you ever venture into codeforces questions, etc? i know they're not really asked in interviews, but will definitely help in improving problem solving skills and are quite fun in general
class Solution: def longestStrChain(self, words: List[str]) -> int: dp = {w: -1 for w in words} # {word: seqLen} def dfs(w): if w in dp: if dp[w] != -1: return dp[w] else: return 0
for i in range(len(w)): dp[w] = max(dp[w], 1 + dfs(w[:i] + w[i+1:])) return dp[w]
res = 0 for i in words: res = max(res, dfs(i)) return res
class Solution:
def longestStrChain(self, words: List[str]) -> int:
from collections import defaultdict
# cache len of chain
cache = defaultdict(int) # word: length of chain
# initiate data
data = sorted(words, key=lambda w: len(w))
for word in data:
# from word, the len of chain is 1 at 1st
cache[word] = 1
for index in range(len(word)):
# construct predecessor
predecessor = word[:index] + word[index + 1:]
if predecessor in cache:
cache[word] = max(cache[word], cache[predecessor] + 1)
return max(cache.values())
I think he makes it complex. You're one is Good. Good work
Love The Stuff Man,Just Learning Leetcode and the way you take things that look complex and make it seem so simple is genius
This is the best explanation of this problem. I couldn't come up witht this.
I don't know what to do , I was not able to think this straight even when I used hint from leetcode , But when I see some part of your solution , I was able to code it my self . I don't know where I am lagging , still not able to do many medium problems
Was waiting for this ! Thanks mate
Love the explanation and python's string slicing
does sorting even help us for this implementation? For the non recursive dp it helps, but for the recursive version it doesn't help since we go thru all the words anyway. can someone confirm this for me cuz im not sure lol.
On second thought, it doesn't help actually. You are right
from collections import defaultdict
from typing import List
class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len) # Sort the words by length to process shorter words first
word_chain = defaultdict(int) # Store the longest chain for each word
for word in words:
for i in range(len(word)):
prev_word = word[:i] + word[i+1:]
word_chain[word] = max(word_chain[word], word_chain[prev_word] + 1)
return max(word_chain.values())
This was easier to understand for me than the solution shown in the video. Great job!
Great Explanation!!! Thanks for Daily Problem solutions!!!!
i know the company in the thumbnail might not matter to you much, but TikTok has actually asked this problem more frequently (according to Leetcode stats) than any other company. So idk why Meta's logo is in the thumbnail when they've asked it very infrequently in comparison
Genius explanation 🎉
Love this explanation. Thanks man. One question, I have been following the 150 Qs from neetcode and then the leetcode 150 most asked. I started Trees yesterday. Is it possible to finish up the list within a month and understand everything? (Given, I have done every topic sequentially and Continuously review 3-4 of them each day) I am really worried about my upcoming interviews. And I find the important ones(Tree, Graph, DP) quite hard😅
literally was looking for a video on this yesterday, and couldnt find on, thats so weird
thanks for the help :)
For time complexity, we will not take sort into consideration?
yoo appreciate the daily upload, will you ever venture into codeforces questions, etc?
i know they're not really asked in interviews, but will definitely help in improving problem solving skills and are quite fun in general
codeforces not worth it unless u're targeting for icpc and you have enough time in hand
@@iscoto4914 basically expand out from interview prep to problem solving in general. or atleast maybe once in a while
Waiting this explanation 🎉
class Solution:
def longestStrChain(self, words: List[str]) -> int:
dp = {w: -1 for w in words} # {word: seqLen}
def dfs(w):
if w in dp:
if dp[w] != -1:
return dp[w]
else:
return 0
for i in range(len(w)):
dp[w] = max(dp[w], 1 + dfs(w[:i] + w[i+1:]))
return dp[w]
res = 0
for i in words:
res = max(res, dfs(i))
return res
can someone explain me the line res = max(res, 1 + dfs(word_index[pred])) pls?
isnt time complexity O(2^N * L * L * N)
Can we solve this using DSU
Yeah, my First thought is also Trie or DSU but the answer is noo once you try to draw the trie you will see why DSU will not work