lass Solution:
    # @param start, a string
    # @param end, a string
    # @param dict, a set of string
    # @return an integer
    def ladderLength(self, start, end, dict):
        g = {}
        dict.add(start)
        dict.add(end)
        dict = [x for x in dict]
        for d in dict:
            g[d] = {}
        for a in range(len(dict)):
            for b in range(len(dict)):
                x, y = dict[a], dict[b]
                dist = sum([1 if x[i] != y[i] else 0 for i in range(len(x))])
                if dist == 1:
                    g[x][y] = 1
                    g[y][x] = 1

        q = [(start, 1)]
        v = {start: 1}
        i = 0
        while i < len(q):
            current, dist = q[i]
            if current == end:
                return dist
            for next in g[current]:
                if next not in v:
                    v[next] = 1
                    q.append((next, dist+1))
            i += 1
        return -1


s = Solution()
d = s.ladderLength('hot', 'dot', set(["hot","dot","dog"]))
print(d)