LeetCode 1048 Longest String Chain

LeetCode 1048 Longest String Chain

You are given an array of words where each word consists of lowercase English letters.

word<sub>A</sub> is a predecessor of word<sub>B</sub> if and only if we can insert exactly one letter anywhere in word<sub>A</sub> without changing the order of the other characters to make it equal to word<sub>B</sub>.

For example, "abc" is a predecessor of "ab<u>a</u>c", while "cba" is not a predecessor of "bcad".

A word chainis a sequence of words [word<sub>1</sub>, word<sub>2</sub>, ..., word<sub>k</sub>] with k >= 1, where word<sub>1</sub> is a predecessor of word<sub>2</sub>, word<sub>2</sub> is a predecessor of word<sub>3</sub>, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

Example 1:

Input: words = [“a”,”b”,”ba”,”bca”,”bda”,”bdca”]
Output: 4
Explanation: One of the longest word chains is [“a”,”ba”,”bda”,”bdca”].

Example 2:

Input: words = [“xbc”,”pcxbcf”,”xb”,”cxbc”,”pcxbc”]
Output: 5
Explanation: All the words can be put in a word chain [“xb”, “xbc“, “cxbc”, “pcxbc”, “pcxbcf“].

Example 3:

Input: words = [“abcd”,”dbqca”]
Output: 1
Explanation: The trivial word chain [“abcd”] is one of the longest word chains.
[“abcd”,”dbqca”] is not a valid word chain because the ordering of the letters is changed.

Constraints: 1 <= words.length <= 1000
1 <= words[i].length <= 16 words[i] only consists of lowercase English letters.

Problem Overview

Get longgest one-character transformation in the given list

Thinking Process

This problem is similar to Word Break (reversed to get neighbors) but it is a multi-source longest path problem.

Steps

1. Loop through each word
2. BFS from each word and get the max distance
3. Get the max of distance

Notes

1. max_dis = 1 by default in BFS
2. To improve the complexity, make the distance map global so that the distance of each node will be calculated once.
   To do that, sort the list from longest to shortest and make sure the it is greedy to get the max distance

Python代码：

def longestStrChain(self, words: List[str]) -> int:
	word_dict, distance = set(words), {}
	max_dis = 0
	words.sort(key=len, reverse=True)  # remember
	for word in words:
		dis = self.bfs(word, word_dict, distance)
		max_dis = max(max_dis, dis)
	return max_dis

def bfs(self, word, word_dict, distance):
	queue = deque([word])
	visited = {word}
	if word in distance:  # remember
		return distance[word]
	distance[word] = 1
	max_dis = 1
	while queue:
		node = queue.popleft()
		for neighbor in self.get_neighbors(node, word_dict):
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
			max_dis = max(max_dis, distance[neighbor])
	return max_dis

def get_neighbors(self, word, word_dict):
	res = []
	for i in range(len(word)):
		new_word = word[:i] + word[i + 1:]
		if new_word in word_dict:
			res.append(new_word)
	return res

Analysis

Though there is a loop and bfs like n^2, actually it is a traversal in a graph. n * L (n is # of nodes, L is max of path
single-source) is the num of edges. Another L is to get neighbors.
Time complexityO(nlogn + n*L2), Space complexityO(n).