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”.
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
Input: [“a”,“b”,“ba”,“bca”,“bda”,“bdca”] Output: 4 Explanation: one of the longest word chain is “a”,“ba”,“bda”,“bdca”.
Solution
func longestStrChain(words []string) int { index := make([][]int, 17) count := make([]int, len(words)) for i,v := range words{ length := len(v) index[length] = append(index[length], i) count[i] = 1 } for length:=1;length<16;length++{ for _,i := range index[length]{ for _,j := range index[length+1]{ if count[j]>count[i]{ continue } if isPredecessor(words[i], words[j]){ count[j] = count[i]+1 } } } } ret:= 0 for _,v := range count{ ret = max(ret, v) } return ret } func isPredecessor(a, b string)bool{ i, j:= 0, 0 diff := 0 for i<len(a) && diff<=1 { if a[i]!=b[j]{ diff ++ }else { i ++ } j ++ } return i==j || diff<=1 } func max(a,b int)int { if a>b{ return a } return b }