# 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](https://3556266963-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LtpqP4Bii7DT_BTd4fN%2Fuploads%2FxMFaMfdR7nHz62XJHsDN%2Fword_chain_graph.jpg?alt=media\&token=85bd7b42-2e6e-4d99-aa1a-0328d4be4b9a)

## 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;