# 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: ["a","b","ba","bca","bda","bdca"]
# Output: 4
# Explanation: one of the longest word chain is "a","ba","bda","bdca".
#
#
# Note:
#
# 1 <= words.length <= 1000
# 1 <= words[i].length <= 16
# words[i] only consists of English lowercase letters.
import collections


class Solution(object):
    def longestStrChain(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        mDict, lenDict, maxLen, minLen = collections.defaultdict(set), collections.defaultdict(set), 0, 1001

        # len(w1) = 1 + len(w2)
        def checkDistance(w1, w2):
            table = [0] * 26
            for c in w1:
                table[ord(c) - ord('a')] += 1

            for c in w2:
                table[ord(c) - ord('a')] -= 1
                if table[ord(c) - ord('a')] < 0:
                    return False

            return sum(table) == 1

        for w in words:
            maxLen, minLen = max(maxLen, len(w)), min(minLen, len(w))
            lenDict[len(w)].add(w)

        for i in xrange(minLen, maxLen):
            for w in lenDict[i]:
                for r in lenDict[i + 1]:
                    if checkDistance(r, w):
                        # form a chain, from smaller to bigger
                        mDict[w].add(r)

        def dfs(w):
            if w in memo:
                return memo[w]
            if w not in mDict:
                memo[w] = 1
                return 1

            t = 0
            for word in mDict[w]:
                t = max(t, 1 + dfs(word))

            memo[w] = t

            return t

        res, memo = 0, {}

        for w in words:
            if w in memo:
                res = max(res, memo[w])
            else:
                res = max(res, dfs(w))

        return res

    # TODO union find


if __name__ == '__main__':
    print Solution().longestStrChain(
        ["ksqvsyq", "ks", "kss", "czvh", "zczpzvdhx", "zczpzvh", "zczpzvhx", "zcpzvh", "zczvh", "gr", "grukmj",
         "ksqvsq", "gruj", "kssq", "ksqsq", "grukkmj", "grukj", "zczpzfvdhx", "gru"])

    print Solution().longestStrChain(["a", "b", "ba", "bca", "bda", "bdca"])
