classSolution {

funlongestStrChain(words:Array<String>):Int {

val wordList= words.toHashSet()

val dp=HashMap<String,Int>()

fundfs(word:String,len:Int):Int {

if (word!in wordList)return0

if ("$word:$len"in dp)return dp["$word:$len"]!!

var res= len

for (iin0 until26) {

for (jin0..word.length) {

val nextWord= word.substring(0, j)+ ('a'+ i)+ word.substring(j, word.length)

res= maxOf(res, dfs(nextWord, len+1))

}

}

dp["$word:$len"]= res

return res

}

var res=1

for (wordin wordList) {

res= maxOf(res, dfs(word,1))

}

return res

}

}

classSolution {

funlongestStrChain(words:Array<String>):Int {

words.sortBy { it.length }

val dp=HashMap<String,Int>()

var res=0

for (wordin words) {

var cur=1

for (iin0 until word.length) {

val nextWord= word.substring(0, i)+ word.substring(i+1)

dp[nextWord]?.let {

cur= maxOf(cur, it+1)

}

}

dp[word]= cur

res= maxOf(res, cur)

}

return res

}

}