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.
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
