Longest String Chain (Dynamic Programming)

longest_string_chain.swift

class Solution {
    func longestStrChain(_ words: [String]) -> Int {
        guard words.count > 1 else { return words.count}
        let words = words.sorted(by: { word1, word2 in
            return word1.count < word2.count
        })
        var map = [String:Int]()
        var maxLength = 0
        for word in words{
            var currentMax = 1 
            
            for j in 0..<word.count {
                var wordCopy = word 
                wordCopy.remove(at: word.index(word.startIndex, offsetBy:j))
                
                if let existingLength = map[wordCopy] {
                    currentMax = max(currentMax, existingLength + 1)
                }                
            }
            map[word] = currentMax
            maxLength = max(maxLength, currentMax)
        }
        return maxLength
    }
}