1048. Longest String Chain

# 1048. Longest String Chain#

## 题目 #

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

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.

## 解题思路 #

• 从这题的数据规模上分析，可以猜出此题是 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
}
``````

Apr 8, 2023