# Given a list of strings words representing an English Dictionary, find the longest word in words that can be built
# one character at a time by other words in words. If there is more than one possible answer, return the longest word
#  with the smallest lexicographical order.
#
# If there is no answer, return the empty string.
# Example 1:
# Input:
# words = ["w","wo","wor","worl", "world"]
# Output: "world"
# Explanation:
# The word "world" can be built one character at a time by "w", "wo", "wor", and "worl".
# Example 2:
# Input:
# words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
# Output: "apple"
# Explanation:
# Both "apply" and "apple" can be built from other words in the dictionary. However, "apple" is lexicographically
# smaller than "apply".
# Note:
#
# All the strings in the input will only contain lowercase letters.
# The length of words will be in the range [1, 1000].
# The length of words[i] will be in the range [1, 30].
import collections


class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """

        def comparator(w1, w2):
            if len(w1) == len(w2):
                return cmp(w2, w1)
            return len(w1) - len(w2)

        wDict = collections.defaultdict(set)
        # for cast ["w"], it should return "w"
        wDict[0].add("")
        words.sort(comparator)

        for w in words:
            wDict[len(w)].add(w)

        def check(w):
            for i in xrange(len(w) - 1, 0, -1):
                if w[0:i] not in wDict[i]:
                    return False

            return True

        for i in reversed(xrange(0, len(words))):
            if check(words[i]):
                return words[i]
        return ""

    # reference, even better
    def longestWord2(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        words.sort()
        maxL, s = 1, set()

        for w in words:
            if len(w) == 1:
                s.add(w)
            elif w[:-1] in s:  # first "w", then check "wo"[:-1] = w
                s.add(w)
                maxL = max(maxL, len(w))

        for w in words:
            if w in s and len(w) == maxL:
                return w

        return ""


if __name__ == '__main__':
    print Solution().longestWord2(
        ["ts", "e", "x", "pbhj", "opto", "xhigy", "erikz", "pbh", "opt", "erikzb", "eri", "erik", "xlye", "xhig",
         "optoj", "optoje", "xly", "pb", "xhi", "x", "o"])
    print Solution().longestWord(["w", "wo", "wor", "worl", "world"])
    print Solution().longestWord2(["w", "wo", "wor", "worl", "world"])
    print Solution().longestWord(["a", "banana", "app", "appl", "ap", "apply", "apple"])
    print Solution().longestWord2(["a", "banana", "app", "appl", "ap", "apply", "apple"])
