1048. Longest String Chain - Explanation

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=lambda w: -len(w))
        word_index = {}  # map word to index
        for i, w in enumerate(words):
            word_index[w] = i

        dp = {}  # index of word -> length of longest chain
        def dfs(i):
            if i in dp:
                return dp[i]
            res = 1
            for j in range(len(words[i])):
                w = words[i]
                pred = w[:j] + w[j+1:]
                if pred in word_index:
                    res = max(res, 1 + dfs(word_index[pred]))
            dp[i] = res
            return res

        for i in range(len(words)):
            dfs(i)
        return max(dp.values())

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        def isPred(w1, w2):
            i = 0
            for c in w2:
                if i == len(w1):
                    return True
                if w1[i] == c:
                    i += 1
            return i == len(w1)

        words.sort(key=len)
        n = len(words)
        dp = [1] * n

        for i in range(1, n):
            for j in range(i - 1, -1, -1):
                if len(words[j]) + 1 < len(words[i]):
                    break
                if len(words[j]) + 1 > len(words[i]) or not isPred(words[j], words[i]):
                    continue
                dp[i] = max(dp[i], 1 + dp[j])

        return max(dp)

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        dp = {}
        res = 0

        for word in words:
            dp[word] = 1
            for i in range(len(word)):
                pred = word[:i] + word[i+1:]
                if pred in dp:
                    dp[word] = max(dp[word], dp[pred] + 1)
            res = max(res, dp[word])

        return res