NeetCode #692LC-1048Medium1-D Dynamic Programming
← Back to All Problems#692 · #1048 · Longest String Chain(最长字符串链)
📌 Problem Statement & Constraints
Given an array of
words, a word chain is a sequence where each word is a predecessor of the next, meaning the next word can be formed by inserting exactly one letter. Return the length of the longest possible word chain. Constraints: 1 <= words.length <= 1000, 1 <= words[i].length <= 16, and all words consist of lowercase English letters.💡 Core Algorithmic Approaches
- Sort the words by length ascending, so every predecessor is processed before its successors.
- Let
dp[w]be the length of the longest chain ending at wordw. - For each word, delete one character at a time to form candidate predecessors; if a candidate is in
dp, extend it. - The answer is the maximum
dpvalue.
💻 Benchmark Python3 Implementation
class Solution:
def longestStrChain(self, words: List[str]) -> int:
words.sort(key=len)
dp = {}
res = 1
for w in words:
best = 1
for i in range(len(w)):
prev = w[:i] + w[i + 1:] # delete one character
if prev in dp:
best = max(best, dp[prev] + 1)
dp[w] = best
res = max(res, best)
return res⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n * L^2): for each word, L deletions each building an O(L) slice.
💾 Space Complexity
O(n * L) for the dictionary keys.
⚠️ Interview Pitfalls & Follow-ups
- Sorting by length descending: predecessors must come first, so ascending length is required.
- Comparing every pair for a one-letter difference: that is O(n^2 * L) and unnecessary; deleting one character per word is O(n * L^2).
- Forgetting the base case: a single-letter word has no predecessor in the dictionary, so
beststarts at 1. - Assuming chains are contiguous in the input: the input order is irrelevant; only lengths matter.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.