问题描述
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.
问题分析
显然，如果以字符串 A1 结尾的最长chain长度已知，那么如果A1为A2的predecessor，则有 f(A2) = f(A1) + 1
如果我们按照题目描述，对一个长度为x的字符，在各个位置添加字符去检测，需要进行 26 * (len(x)+1) 次尝试才能确定是否为某个给定字符的predecessor，效率太低；
所以这里我们反过来计算，对于长度为x的字符串，依次去掉各个位上的字符，去check此时这个长度为x-1的字符是否在给定字符串集合中
综上，我们采用dp方式进行如下求解：
示例代码
func longestStrChain(words []string) int {
ans := 1
// sort by length, asc
sort.Slice(words, func(i, j int) bool {
return len(words[i]) < len(words[j])
})
// 字符串hash，便于快速check字符串是否存在
m := make(map[string]struct{})
// dp[i]表示以字符串i结尾的最长chain长度
dp := make(map[string]int)
for _, v := range words {
m[v] = struct{}{}
// 初始化为1
dp[v] = 1
}
// 从第二个字符串开始计算
for i := 1; i < len(words); i++ {
for j := 0; j < len(words[i]); j++ {
// 逐位去掉words[i]的字符，check新的字符串是否存在
word := words[i][0:j] + words[i][j+1:]
if _, ok := m[word]; ok {
// 更新dp值
dp[words[i]] = max(dp[words[i]], dp[word]+1)
// 更新计算过程中的极大值
ans = max(ans, dp[words[i]])
}
}
}
return ans
}
func max(a int, b int) int {
if a > b {
return a
}
return b
}