[算法] Word Ladder

Question
Word Ladder

Question Description

Given two words (start and end), and a dictionary, find the shortest transformation sequence from start to end, output the length of the sequence.
Transformation rule such that:

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary. (Start and end words do not need to appear in the dictionary )

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Language
Python 3

Data structure description
""" Definition for a Directed graph node class DirectedGraphNode: def __init__(self, x): self.label = x self.neighbors = [] """

Thinking Solution
Replace the word to generate next word then confirm with dict and visited. Finial can get distance.

Solution
class Solution: """ @param: start: a string @param: end: a string @param: dict: a set of string @return: An integer """ def ladderLength(self, start, end, dict): dict.add(end) queue = collections.deque([start]) visited = set([start]) distance = 0 while queue: distance += 1 for i in range(len(queue)): word = queue.popleft() if word == end: return distance for w in self.get_next_words(word): if w in visited or w not in dict: continue visited.add(w) queue.append(w) return -1 def get_next_words(self, word): output = [] for i in range(len(word)): left, right = word[0:i], word[i+1:] for new_word in 'abcdefghijklmnopqrstuvwxyz': if new_word == word[i]: continue output.append(left+new_word+right) return output

Reference Link
https://www.lintcode.com/problem/word-ladder/description