|
| 1 | +from collections import defaultdict |
| 2 | +class Solution(object): |
| 3 | + def ladderLength(self, beginWord, endWord, wordList): |
| 4 | + """ |
| 5 | + :type beginWord: str |
| 6 | + :type endWord: str |
| 7 | + :type wordList: List[str] |
| 8 | + :rtype: int |
| 9 | + """ |
| 10 | + |
| 11 | + if endWord not in wordList or not endWord or not beginWord or not wordList: |
| 12 | + return 0 |
| 13 | + |
| 14 | + # Since all words are of same length. |
| 15 | + L = len(beginWord) |
| 16 | + |
| 17 | + # Dictionary to hold combination of words that can be formed, |
| 18 | + # from any given word. By changing one letter at a time. |
| 19 | + all_combo_dict = defaultdict(list) |
| 20 | + for word in wordList: |
| 21 | + for i in range(L): |
| 22 | + # Key is the generic word |
| 23 | + # Value is a list of words which have the same intermediate generic word. |
| 24 | + all_combo_dict[word[:i] + "*" + word[i+1:]].append(word) |
| 25 | + |
| 26 | + |
| 27 | + # Queue for BFS |
| 28 | + queue = collections.deque([(beginWord, 1)]) |
| 29 | + # Visited to make sure we don't repeat processing same word. |
| 30 | + visited = {beginWord: True} |
| 31 | + while queue: |
| 32 | + current_word, level = queue.popleft() |
| 33 | + for i in range(L): |
| 34 | + # Intermediate words for current word |
| 35 | + intermediate_word = current_word[:i] + "*" + current_word[i+1:] |
| 36 | +
|
| 37 | + # Next states are all the words which share the same intermediate state. |
| 38 | + for word in all_combo_dict[intermediate_word]: |
| 39 | + # If at any point if we find what we are looking for |
| 40 | + # i.e. the end word - we can return with the answer. |
| 41 | + if word == endWord: |
| 42 | + return level + 1 |
| 43 | + # Otherwise, add it to the BFS Queue. Also mark it visited |
| 44 | + if word not in visited: |
| 45 | + visited[word] = True |
| 46 | + queue.append((word, level + 1)) |
| 47 | + all_combo_dict[intermediate_word] = [] |
| 48 | + return 0 |
0 commit comments