Word Ladder

127 Word Ladder

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

Only one letter can be changed at a time 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.

def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
    if endWord not in wordList: return 0
    wordDict = set(wordList)
    visit = set()
    q = []
    count = 0
    
    q.append(beginWord)
    
    while q:
        size = len(q)
        count += 1
        for i in range(size):
            word = q.pop(0)
            if word == endWord:
                return count
            for next_word in self.getNext(word, wordDict):
                if next_word not in visit:
                    q.append(next_word)
                    # 假若next_word符合條件但是已經看過代表他會
                    # 形成更遠的分支，不予考慮
                    visit.add(next_word)
                    
    return 0


def getNext(self, word, wordDict):
    next_list = []

    for i in range(len(word)):
        for j in range(26):
            ch = chr(ord('a') + j)
            if ch == word[i]: continue
            new_word = word[:i] + ch + word[i+1:]
            if new_word in wordDict:
                next_list.append(new_word)

    return next_list

126 Word Ladder II

Example Given: start = "hit" end = "cog" dict = ["hot","dot","dog","lot","log"] Return [ ["hit","hot","dot","dog","cog"], ["hit","hot","lot","log","cog"] ]

• Hint: 1. Use BFS from end to start to record the distance of node to end

  • 2. DFS to record all shortest path

• Map the distance of node to end

• Map surrounding Nodes

• 注意在bfs時先把

def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
    if endWord not in wordList: return []
    
    self.wordDict = set(wordList)
    # Add beginWord to wordDict, otherwise it will not be update when BFS
    self.wordDict.add(beginWord)
    self.neighbors = defaultdict(list)
    self.distance = defaultdict(int)
    self.ans = []
    
    # use bfs to traverse from end to start, and record the nerghbors of each node and distance from end to each node
    # distance will be update as the shortest distance to end
    self.bfs(beginWord, endWord)
    # dfs to find out the route
    self.dfs([beginWord], endWord)
    
    return self.ans


def dfs(self, l, endWord):
    word = l[-1]
    if word == endWord:
        self.ans.append(l.copy())
    
    for next_word in self.neighbors[word]:
        l.append(next_word)
        
        # only go to next level if on the correct route
        if self.distance[word] == self.distance[next_word] + 1:
            self.dfs(l, endWord)
        l.pop()
    
    
def bfs(self, beginWord, endWord):
    q = []
    q.append(endWord)
    flag = False
    
    while q:
        if flag: break
        size = len(q)
        for i in range(size):
            word = q.pop(0)
            for next_word in self.getNext(word):
                if next_word == beginWord:
                    flag = True
                
                self.neighbors[next_word].append(word)
                # If we have seen the node distance means this one if farther distance. Not update
                if next_word not in self.distance:
                    self.distance[next_word] = self.distance[word] + 1
                    q.append(next_word)
                    
                    
def getNext(self, word):
    next_list = []
    for i in range(len(word)):
        for j in range(26):
            ch = chr(ord('a') + j)
            if word[i] == ch: continue
            new_word = word[:i] + ch + word[i+1:]
            if new_word in self.wordDict:
                next_list.append(new_word)
                
    return next_list