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())
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😅
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())
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
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
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