# Longest String Chain

## Question ([LC.1048](https://leetcode.com/problems/longest-string-chain/)) 

> Given a list of words, find the length of the longest word chain. 

A word chain is defined as `word_1, word_2, ..., word_n` and `word_i+1` has exactly one more letter than `word_i`. 

## Examples

```
I: words = ["a","b","ba","bca","bda","bdca"]
O: 4 (a -> ba -> bca -> bdca)

I: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
O: 5

I: words = ["abcd","dbqca"]
O: 1
```

## Approach 

Drawing out the nodes in this search graph is going to be very helpful. Each word can be a node in the graph and the edges are the chains between words. 

![Words Search Graph](/files/9pxYTok5lm8wO5xeEyqd)

## Graph Search

```python
from collections import defaultdict

# 1. convert the words list to a map (level) => list of words
# 2. for every node return the longest path length 
# 3. helper for finding length for each node path 

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        level_to_words: Dict[int, List[str]] = defaultdict(list)
        for word in words:
            level_to_words[len(word)].append(word)
        
        max_len = 0
        for word in words:
            word_path = 1 + self.word_path_helper(level_to_words, word)
            max_len = max(max_len, word_path)
        
        return max_len
    
    def is_next_word(self, word, next_word) -> bool:
        word_list = list(word)
        next_word_list = list(next_word)
        i = 0
        j = 0
        diff = 0
        while i < len(word) and j < len(next_word):
            if word_list[i] == next_word_list[j]:
                i += 1
                j += 1
            else:
                j += 1
                diff += 1
        # diff += len(next_word) - 1 - j
        return diff <= 1
    
    def word_path_helper(
        self, 
        level_to_words: Dict[int, List[str]],
        word: str
    ) -> int:
        # base case 
        
        # divide 
        max_path = 0
        if len(word) + 1 in level_to_words:
            for next_word in level_to_words[len(word) + 1]:
                if self.is_next_word(word, next_word):  
                    path = 1 + self.word_path_helper(level_to_words, next_word)
                    max_path = max(max_path, path)
        
        return max_path
```

TLE 78 / 79 tests passed&#x20;

## Memoized Search&#x20;

```python
class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        level_to_words: Dict[int, List[str]] = defaultdict(list)
        for word in words:
            level_to_words[len(word)].append(word)
        
        memo: Dict[str, int] = {}
        
        max_len = 0
        for word in words:
            word_path = 1 + self.word_path_helper(level_to_words, word, memo)
            max_len = max(max_len, word_path)
        return max_len
    
    def is_next_word(self, word, next_word) -> bool:
        word_list = list(word)
        next_word_list = list(next_word)
        i = 0
        j = 0
        diff = 0
        while i < len(word) and j < len(next_word):
            if word_list[i] == next_word_list[j]:
                i += 1
                j += 1
            else:
                j += 1
                diff += 1
        return diff <= 1
    
    def word_path_helper(
        self, 
        level_to_words: Dict[int, List[str]],
        word: str,
        memo: Dict[str, int]
    ) -> int:
        # base case 
        if word in memo:
            return memo[word]
        # divide 
        max_path = 0
        if len(word) + 1 in level_to_words:
            for next_word in level_to_words[len(word) + 1]:
                if self.is_next_word(word, next_word):  
                    path = 1 + self.word_path_helper(level_to_words, next_word, memo)
                    max_path = max(max_path, path)
        memo[word] = max_path
        return max_path
```

Now the runtime is bounded by the size of the input&#x20;


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zedive.gitbook.io/project-l/part-2/dynamic_programming/tree-dp/longest-string-chain.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.