題目

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.

題目大意

給出一個單詞列表，其中每個單詞都由小寫英文字母組成。如果我們可以在 word1 的任何地方添加一個字母使其變成 word2，那麼我們認為 word1 是 word2 的前身。例如，"abc" 是 "abac" 的前身。詞鏈是單詞 [word_1, word_2, ..., word_k] 組成的序列，k >= 1，其中 word_1 是 word_2 的前身，word_2 是 word_3 的前身，依此類推。從給定單詞列表 words 中選擇單詞組成詞鏈，返回詞鏈的最長可能長度。

解題思路

• 從這題的數據規模上分析，可以猜出此題是 DFS 或者 DP 的題。簡單暴力的方法是以每個字符串為鏈條的起點開始枚舉之後的字符串，兩兩判斷能否構成滿足題意的前身字符串。這種做法包含很多重疊子問題，例如 a 和 b 能構成前身字符串，以 c 為起點的字符串鏈條可能用到 a 和 b，以 d 為起點的字符串鏈條也可能用到 a 和 b。順其自然，考慮用 DP 的思路解題。
• 先將 words 字符串數組排序，然後用 poss 數組記錄下每種長度字符串的在排序數組中的起始下標。然後逆序往前遞推。因為初始條件只能得到以最長字符串為起始的字符串鏈長度為 1 。每選擇一個起始字符串，從它的長度 + 1 的每個字符串 j 開始比較，是否能為其前身字符串。如果能構成前身字符串，那麼 dp[i] = max(dp[i], 1+dp[j])。最終遞推到下標為 0 的字符串。最終輸出整個遞推過程中的最大長度即為所求。

參考代碼

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
}