LeetCode: Longest String Chain

// https://code.dennyzhang.com/longest-string-chain
// Basic Ideas: LIS dp + hashmap
//
//  Notice: instead of adding a character, try to delete one
//  The sequence doesn't matter: There might be a chain of s[i] -> s[j] with j<i
//
// Complexity: Time O(n*log(n)), Space O(n)
import "sort"
func longestStrChain(words []string) int {
    sort.Slice(words , func(i, j int) bool {
        return len(words[i])<len(words[j])
    })
    m := map[string]int{}
    dp := make([]int, len(words))
    res := 0
    dp[0] = 1
    m[words[0]] = 0
    for i:=1; i<len(words); i++ {
        word := words[i]
        max := 1
        for j, _ := range word {
            word2 := word[0:j]+word[j+1:]
            if v, ok := m[word2]; ok {
                if dp[v]+1>max {
                    max = dp[v]+1
                }
            }
        }
        dp[i] = max
        m[word] = i
        if max > res {
            res = max
        }
    }
    return res
}