Leetcode Problem 1048. Longest String Chain

1048. Longest String Chain

Leetcode Solutions

Approach: Top-Down Dynamic Programming (Recursion + Memoization)

  1. Initialize a set (wordsPresent) and add all the words in the list to the set.
  2. Initialize a map (memo) to store the length of the longest word chain for each word.
  3. Iterate over the list and for each word, perform a depth-first search.
  4. In the DFS, if the currentWord is in the memo, return its value.
  5. Otherwise, initialize maxLength to 1.
  6. Iterate over the length of currentWord, creating newWord by removing one character at a time.
  7. If newWord is in wordsPresent, perform DFS on newWord and update maxLength.
  8. Store maxLength in memo for currentWord.
  9. Return maxLength.
UML Thumbnail

Approach: Bottom-Up Dynamic Programming

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...