Easy to understand, python BFS, graph on bank nodes


  • 0

    The problem can be solved by making graph on bank nodes, and also inserting start in this graph. Since end is already present in the bank we dont need to add end explicitly here. We mark an edge between two words if there is change of only one character in these two words, which is what hasEdge check. The edge is added in both the directions since it is undirected graph. Then we edges for start node. Once the graph is complete, just call BFS to count the number of steps to return the mutation.

    class Solution(object):
        def minMutation(self, start, end, bank):
            """
            :type start: str
            :type end: str
            :type bank: List[str]
            :rtype: int
            """
            def hasEdge(s, t):
                if len(s) != len(t): return False
                count = 0
                for i, c in enumerate(s):
                    if c != t[i]:
                        count += 1
                
                return count == 1
            
            def bfs(start, end, graph, visited):
                
                q = collections.deque()
                q.append(start)
                q.append('#')
                visited[start] = 1
                
                step = 0
                while q:
                    node = q.popleft()
                    if node == "#":
                        if not q: break
                        q.append('#')
                        step += 1
                        
                    for neigh in list(graph[node]):
                        if not visited[neigh]:
                            visited[neigh] = 1
                            q.append(neigh)
                            if neigh == end: return step+1
                
                return -1
                
            
            if not bank or end not in bank: return -1
            if start == end: return 0
            
            graph, n = collections.defaultdict(set), len(bank)
            for i in xrange(n):
                for j in xrange(i+1, n):
                    if hasEdge(bank[i], bank[j]):
                        graph[bank[i]].add(bank[j])
                        graph[bank[j]].add(bank[i])
            
            visited = {}
            visited[start], visited[end] = 0, 0
            
            for i in xrange(n):
                visited[bank[i]] = 0
                if hasEdge(start, bank[i]):
                    graph[start].add(bank[i])
                    graph[bank[i]].add(start)
            
            return bfs(start, end, graph, visited)
                    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.