動機

重點是怎麼找下一個!! 讓每一次擴展狀態都是有用的，少做許多無用功

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words beginWord -> s1 -> s2 -> ... -> sk such that:

  • Every adjacent pair of words differs by a single letter.
  • Every si for 1 <= i <= k is in wordList. Note that beginWord does not need to be in wordList.
  • sk == endWord

Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

 

Example 1:

Input: beginWord = hit, endWord = cog, wordList = [hot,dot,dog,lot,log,cog]Output: 5Explanation: One shortest transformation sequence is hit -> hot -> dot -> dog -> cog, which is 5 words long.

Example 2:

Input: beginWord = hit, endWord = cog, wordList = [hot,dot,dog,lot,log]Output: 0Explanation: The endWord cog is not in wordList, therefore there is no valid transformation sequence.

 

Constraints:

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.

Sol1: Trie + BFS

用trie來看是不是下一個點，不過真的很慢

class Solution:
    def buildTrie(self,ws):
        for w in ws:
            tmp = self.trie
            for c in w:
                if c not in tmp[1]:
                    tmp[1][c] = [False, {}]
                tmp = tmp[1][c]
            tmp[0] = True
    def getCandidates(self,root,w,i=0,can="",acc=1):
        if i == len(w):
            return [can] if root[0] or acc > 0 else []
        else:
            ret = []
            for k in root[1]:
                if k == w[i]:
                    ret += self.getCandidates(root[1][k],w,i+1,can+k,acc)
                elif acc > 0:
                    ret += self.getCandidates(root[1][k],w,i+1,can+k,acc-1)
            return ret
    def bfs(self,start,end):
        ret = 0
        q = deque([[start]])
        seen = set()
        while q:
            print(q)
            ws = q.popleft()
            if end in ws:
                return ret+1
            seen.update(ws)
            candidates = []
            for w in ws:
                tmp = self.getCandidates(self.trie,w)
                candidates += [s for s in tmp if s not in seen]
            if candidates:
                q.appendleft(candidates)
                ret += 1
        return 0
        
    def ladderLength(self, start: str, end: str, ws: List[str]) -> int:
        self.trie = [False, {}]
        self.buildTrie(ws)
        return self.bfs(start,end)

Sol2: Hash + BFS

剛剛是從起點去比每個單字，這樣擴張(queue變大)的速度就會變慢，同時還會出現許多已經比對過的，所以改成用碼掉一個字來看能不能到 dog => d*g <= dig

這樣就不用花時間去比本來就不是的單字，這個就是比第一個快的關鍵，每一次擴展狀態就是存在的，而不是先看是不是對的狀態再擴展

class Solution(object):
    def ladderLength(self, beginWord, endWord, wordList):

        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        L = len(beginWord)

        all_combo_dict = defaultdict(list)
        for word in wordList:
            for i in range(L):
                all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)

        queue = collections.deque([(beginWord, 1)])
        visited = {beginWord: True}
        while queue:
            current_word, level = queue.popleft()
            for i in range(L):
                intermediate_word = current_word[:i] + "*" + current_word[i+1:]

                for word in all_combo_dict[intermediate_word]:
                    if word == endWord:
                        return level + 1

                    if word not in visited:
                        visited[word] = True
                        queue.append((word, level + 1))
        return 0

Sol: Hash + BFS *2

從起點與終點一起刷，只要有交會就是有

from collections import defaultdict
class Solution(object):
    def __init__(self):
        self.length = 0
        self.all_combo_dict = defaultdict(list)

    def visitWordNode(self, queue, visited, others_visited):
        current_word, level = queue.popleft()
        for i in range(self.length):
            intermediate_word = current_word[:i] + "*" + current_word[i+1:]

            for word in self.all_combo_dict[intermediate_word]:
                if word in others_visited:
                    return level + others_visited[word]
                if word not in visited:
                    visited[word] = level + 1
                    queue.append((word, level + 1))
        return None

    def ladderLength(self, beginWord, endWord, wordList):
        """
        :type beginWord: str
        :type endWord: str
        :type wordList: List[str]
        :rtype: int
        """

        if endWord not in wordList or not endWord or not beginWord or not wordList:
            return 0

        self.length = len(beginWord)

        for word in wordList:
            for i in range(self.length):
                self.all_combo_dict[word[:i] + "*" + word[i+1:]].append(word)


        queue_begin = collections.deque([(beginWord, 1)]) # BFS starting from beginWord
        queue_end = collections.deque([(endWord, 1)]) # BFS starting from endWord

        visited_begin = {beginWord: 1}
        visited_end = {endWord: 1}
        ans = None

        while queue_begin and queue_end:

            # One hop from begin word
            ans = self.visitWordNode(queue_begin, visited_begin, visited_end)
            if ans:
                return ans
            # One hop from end word
            ans = self.visitWordNode(queue_end, visited_end, visited_begin)
            if ans:
                return ans

        return 0