1048. Longest String Chain

Problem

Given a list of words, each word consists of English lowercase letters.

Let's say word1 is a predecessor of word2 if and only if we can add exactly one letter anywhere in word1 to make it equal to word2. For example, "abc" is a predecessor of "abac".

A word chain is a sequence of words [word_1, word_2, ..., word_k] with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on.

Return the longest possible length of a 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 chain is "a","ba","bda","bdca".

Example 2:

Input: words = ["xbc","pcxbcf","xb","cxbc","pcxbc"]
Output: 5

Constraints:

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

Problem Summary

Given a list of words, each word consists of lowercase English letters. If we can add one letter anywhere in word1 to make it become word2, then we consider word1 to be a predecessor of word2. For example, "abc" is a predecessor of "abac". A word chain is a sequence composed of words [word_1, word_2, ..., word_k], with k >= 1, where word_1 is a predecessor of word_2, word_2 is a predecessor of word_3, and so on. Choose words from the given list words to form a word chain, and return the longest possible length of the word chain.

Solution Approach

• Analyzing the data constraints of this problem, we can infer that it is a DFS or DP problem. A simple brute-force method is to take each string as the starting point of a chain, enumerate the subsequent strings, and check pairwise whether they can form a predecessor relationship satisfying the problem statement. This approach contains many overlapping subproblems. For example, if a and b can form a predecessor relationship, then the string chain starting from c may use a and b, and the string chain starting from d may also use a and b. Naturally, we consider solving it with DP.
• First sort the words string array, then use the poss array to record the starting index of strings of each length in the sorted array. Then perform reverse recurrence from back to front. This is because the initial condition can only determine that the string chain length starting with the longest strings is 1. For each chosen starting string, compare it with every string j of length + 1 to see whether it can be its predecessor. If it can form a predecessor relationship, then dp[i] = max(dp[i], 1+dp[j]). Finally, the recurrence proceeds to the string at index 0. The maximum length throughout the entire recurrence process is the answer.

Code

package leetcode

import "sort"

func longestStrChain(words []string) int {
	sort.Slice(words, func(i, j int) bool { return len(words[i]) < len(words[j]) })
	poss, res := make([]int, 16+2), 0
	for i, w := range words {
		if poss[len(w)] == 0 {
			poss[len(w)] = i
		}
	}
	dp := make([]int, len(words))
	for i := len(words) - 1; i >= 0; i-- {
		dp[i] = 1
		for j := poss[len(words[i])+1]; j < len(words) && len(words[j]) == len(words[i])+1; j++ {
			if isPredecessor(words[j], words[i]) {
				dp[i] = max(dp[i], 1+dp[j])
			}
		}
		res = max(res, dp[i])
	}
	return res
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func isPredecessor(long, short string) bool {
	i, j := 0, 0
	wasMismatch := false
	for j < len(short) {
		if long[i] != short[j] {
			if wasMismatch {
				return false
			}
			wasMismatch = true
			i++
			continue
		}
		i++
		j++
	}
	return true
}