卖萌的弱渣

I am stupid, I am hungry.

Wrod Ladder

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

  1. Only one letter can be changed at a time
  2. Each intermediate word must exist in the dictionary

Notice

Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters.

Example

Given: start = “hit”

end = “cog”

dict = [“hot”,“dot”,“dog”,“lot”,“log”]

As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Solution

  • Time O(n)
  • Use BFS and a special queue to solve this problem
(Word-Ladder.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import collections
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):
        # write your code here
        # queue: <word,level>
        queue = collections.deque([(start,1)])
        # if you dont add end into the dict, you will never find the final destination
        dict.add(end)

        while len(queue) != 0:
            curr = queue.popleft()
            level = curr[1]
            cur = curr[0]
            if cur == end:
                return level
            else:
                wordL = list(cur)
                for i in 'abcdefghijklmnopqrstuvwxyz':
                    for j in range(len(wordL)):
                        left_word = cur[:j]
                        right_word = cur[j+1:]
                        if i != cur[j]:
                            # new_word is the word may exist in the dict
                            new_word = left_word+i+right_word
                            if new_word in dict:
                                queue.append((new_word,level+1))
                                dict.remove(new_word)
        return 0