Word Ladder

Question

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

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.

Note

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

Thoughts

word ladder

一开始看到string会以为是类似array的问题，但是其实是graph的问题 找最短路径，应该用BFS而不是DFS BFS搜索，最先搜索到的一定是最短路径

这种题，肯定是每次改变单词的一个字母，然后逐渐搜索，很多人一开始就想到用dfs，其实像这种求最短路径、树最小深度问题bfs最适合，可以参考我的这篇博客bfs（层序遍历）求二叉树的最小深度。本题bfs要注意的问题：

1. 和当前单词相邻的单词是：对当前单词改变一个字母且在字典中存在的单词

一开始我使用每个dict里面的word和curr比较是否是neighbour的方式，但是这个会随着dict越大计算次数越多，会超时

使用每个位置改变26个字母来找neighbours的方法，只需要使用固定的26 * len(word)的time

1. 找到一个单词的相邻单词，加入bfs队列后，要从字典中删除，因为不删除的话会造成类似于hog->hot->hog的死循环。而删除对求最短路径没有影响，因为我们第一次找到该单词肯定是最短路径，即使后面其他单词也可能转化得到它，路径肯定不会比当前的路径短（如果要输出所有最短路径，则不能立即从字典中删除，具体见下一题）

Solution

BFS的方法，但是这个方法超时

from collections import deque
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
        if not start or not end or not dict:                                           
            return None
        #bfs
        level = 1
        queue = deque()
        queue.append([start, level])
        while queue:
            c = queue.popleft()
            curr = c[0]
            curLev= c[1]
            if self.isNeighbour(end, curr):
                return curLev + 1
            for word in dict:
                if curr != word and self.isNeighbour(curr, word):
                    queue.append([word, curLev + 1])
        return None

    def isNeighbour(self, curr, word):
        len1 = len(curr)
        len2 = len(word)
        if len1 != len2:
            return False
        else:
            diff = 0
            for i in range(len1):
                if curr[i] != word[i]:
                    diff += 1
                if diff > 1:
                    return False
            return True

使用改变26个字母的方法查找，并且删掉已经用的词，不超时

from collections import deque
from string import ascii_lowercase
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
        if not start or not end or not dict:                                           
            return None
        #bfs
        used = {}
        level = 1
        queue = deque()
        queue.append([start, level])
        while queue:
            c = queue.popleft()
            curr = c[0]
            curLev= c[1]
            if self.isNeighbour(end, curr):
                return curLev + 1
            removeQueue = []
            ns = self.getNeighbours(curr, dict)
            for word in ns:
                if curr != word:
                        queue.append([word, curLev + 1])
                        removeQueue.append(word)
            #delete the word already used
            for word in removeQueue:
                dict.remove(word)
        return None

    def getNeighbours(self, curr, dict):
        #26 characters(a-z)
        neighbours = []
        for i in range(len(curr)):
            for c in ascii_lowercase:
                s = list(curr)
                s[i] = c
                s = "".join(s)
                if s in dict:
                    neighbours.append(s)
        return neighbours