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