Longest String Chain

Question (LC.1048)

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

Graph Search

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

Memoized Search

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