Shortest Classifier

给出几个二进制数…如何找到最小的连续bit位数以区别这几个二进制数？比如我1000 0100 0010这三个数…我只要前两位就能区别了。

思路： 解法就是我们建一个Trie树，把所有的数都存到Trie里。在这个建树的过程中我们找到一个最晚分叉的位置和一个最早分叉的位置

怎么找这个最晚分叉的位置呢。就是我们在造树过程中，如果遇到其中一个节点，树里面没有。那么这个深度就是对于这个数来说我们需要的classify的节点深度。 所有的这些深度中，最大的，就是我们要找的最小深度。（有点难理解哈。）

然后我们要找这个树最早是在哪里分叉的来得到minDepth。这样我们从minDepth取到maxDepth就可以把最短的给找出来了。

以1000 0100 0010举例。先把1000放到trie里面。 所以深度是1，因为第一个node我们就要新建。然后接着放0100，深度也是1，因为第一个Node我们要新建。接着放0010，这时候深度为2，因为0已经在Trie中了。所以maxDepth是2.而第一个就分叉了，随意minDepth是1。

class Solution():
    def minPrefixLength(self, nums):
        """
        :type nums: List[str]
        :rtype: int
        """
        trie = {}
        maxDepth = 0

        for num in nums:
            depth, checked = 0, False
            root = trie
            for c in num:
                # when node is not in trie
                if c not in root:
                    # only compare depth of first node we create
                    if not checked:
                        maxDepth = max(depth, maxDepth)
                        checked = True
                    root[c] = {}
                root = root[c]
                # increase depth
                depth += 1

        # get the min index of the subarray
        root = trie
        minDepth = 0
        while len(root)==1:
            minDepth += 1
            root = root.items()[0][1]

        return maxDepth+1 - minDepth

nums = ['11110100', '11111000', '11111100']
so = Solution()
ans = so.minPrefixLength(nums)
print ans