Python : Crystal clear solution (BFS + DFS) using custom Graph ADT


#1
class Vertex:
    def __init__(self, key, val=None):
        self.key = key
        self.val = val
        self.color = 'white'
        self.distance = -1
        self.pred = None
        self.connectedTo = {}

    def getPredecessor(self):
        return self.pred

    def getKey(self):
        return self.key

    def getVal(self):
        return self.val

    def setVal(self, val):
        self.val = val

    def setPredecessor(self, pred):
        self.pred = pred

    def getColor(self):
        return self.color

    def setColor(self, c):
        self.color = c

    def getDistance(self):
        return self.distance

    def setDistance(self, dist):
        self.distance = dist

    def addNeighbor(self, nbr, weight=0):
        self.connectedTo[nbr] = weight

    def getConnections(self):
        return self.connectedTo.keys()

    def getKey(self):
        return self.key

    def getWeight(self, nbr):
        return self.connectedTo[nbr]

    def __repr__(self):
        if self.val:
            return "{} : {}".format(self.key, self.val)
        else:
            return "{}".format(self.key)


class Graph:
    def __init__(self):
        self.vertices = {}
        self.numVertices = 0
        self.numEdges = 0

    def addVertex(self, key, val=None):
        self.numVertices += 1
        nv = Vertex(key, val)
        self.vertices[key] = nv
        return nv

    def getVertex(self, key):
        return self.vertices.get(key)

    def __contains__(self, n):
        return n in self.vertices

    def addEdge(self, f, t, weight=0):
        if f not in self.vertices:
            nv = self.addVertex(f)
        if t not in self.vertices:
            nv = self.addVertex(t)

        self.vertices[f].addNeighbor(self.vertices[t], weight)
        self.numEdges += 1

    def getVertices(self):
        return self.vertices.keys()

    def __iter__(self):
        return iter(self.vertices.values())


from Queue import Queue


class Solution:
    # @param start : string
    # @param end : string
    # @param dictV : list of strings
    # @return an integer
    def buildGraph(self, wordlist):
        buckets = {}
        g = Graph()

        for word in wordlist:
            for i in range(len(word)):
                bucket = word[:i] + '_' + word[i + 1:]
                if bucket != '_':
                    if bucket in buckets:
                        buckets[bucket].append(word)
                    else:
                        buckets[bucket] = [word]

        for bucket in buckets.keys():
            for w1 in buckets[bucket]:
                for w2 in buckets[bucket]:
                    if w1 != w2:
                        g.addEdge(w1, w2)

        return g

    def bfs(self, start):
        start.setDistance(0)
        start.setColor('gray')
        vq = Queue()
        vq.put(start)
        while not vq.empty():
            cv = vq.get()
            for nbr in cv.getConnections():
                if nbr.getColor() == 'white':
                    nbr.setColor('gray')
                    nbr.setPredecessor(cv)
                    nbr.setDistance(cv.getDistance() + 1)
                    vq.put(nbr)
            cv.setColor('black')

    def dfs(self, graph, path, res, currentVertex, end):
        if currentVertex.getKey() == end:
            res.append(path[:])
        else:
            for nbr in currentVertex.getConnections():
                if nbr.getDistance() > currentVertex.getDistance():
                    self.dfs(graph, path + [nbr.key], res, nbr, end)

    def findLadders(self, start, end, dictV):
        g = self.buildGraph(dictV)

        if start == end:
            return [[start]]
        if start not in g:
            return []

        res = []

        self.bfs(g.getVertex(start))

        for vertex in g:
            vertex.setColor('white')

        self.dfs(g, [start], res, g.getVertex(start), end)

        return res