Longest String Chain - Leetcode 1048 - Python

[@danielsun716]

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

[@iscoto4914]

I think he makes it complex. You're one is Good. Good work

[@troytaylor4719]

Love The Stuff Man,Just Learning Leetcode and the way you take things that look complex and make it seem so simple is genius

[@reggiehurley1479]

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.

[@shrn]

On second thought, it doesn't help actually. You are right

[@devkumar9889]

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

[@bidishadas832]

This is the best explanation of this problem. I couldn't come up witht this.

[@AchyutSarmaB]

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

[@Raymond-Wu]

This was easier to understand for me than the solution shown in the video. Great job!

[@michelle_tsai_drums]

Love the explanation and python's string slicing

[@aasheesh6001]

Great Explanation!!! Thanks for Daily Problem solutions!!!!

[@gauthamsakthiveeran7946]

Was waiting for this ! Thanks mate

[@rajanmaheshwari]

For time complexity, we will not take sort into consideration?

[@vs3.14]

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😅

[@VidyaBhandary]

Genius explanation 🎉

[@phpostrich]

literally was looking for a video on this yesterday, and couldnt find on, thats so weird

[@phpostrich]

thanks for the help :)

[@iscoto4914]

can someone explain me the line res = max(res, 1 + dfs(word_index[pred])) pls?

[@binfos7434]

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

[@簡崇宇-b5z]

Waiting this explanation 🎉

[@memevideos7461]

isnt time complexity O(2^N * L * L * N)

[@roywastaken]

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

[@uddiptakalita3006]

Can we solve this using DSU

[@sumitsharma6738]

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

[@saiashishvure]

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

[@iscoto4914]

codeforces not worth it unless u're targeting for icpc and you have enough time in hand

[@saiashishvure]

@@iscoto4914 basically expand out from interview prep to problem solving in general. or atleast maybe once in a while