Блог

Я имитирую двунаправленное решение проблемы wordLadder в leetcode Word Ladder — LeetCode

Учитывая два слова (начальное слово и конечное слово) и список слов в словаре, найдите длину кратчайшей последовательности преобразований от начального слова до конечного слова, такой, что:

1. Одновременно может быть изменена только одна буква.
2. Каждое преобразованное слово должно существовать в списке слов. Обратите внимание, что beginWord не является преобразованным словом.

Примечание:

• Верните 0, если такой последовательности преобразования нет.
• Все слова имеют одинаковую длину.
• Все слова содержат только строчные буквенные символы.
• Вы можете предположить, что в списке слов нет дубликатов.
• Вы можете предположить, что beginWord и endWord не являются пустыми и не совпадают.

Пример 1:

 Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
  

Пример 2:

 Input:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.
  

решение

 class Solution2(object):
    def ladderLength(self, beginWord, endWord, wordList):
        #base case
        if (endWord not in wordList) or (not endWord) or (not beginWord) or (not wordList):
            return 0
        size = len(beginWord)
        word_set = set(wordList)    
        forwards, backwards = {beginWord}, {endWord}
        visited = set()
        step = 0
        while forwards and backwards:
            step  = 1 #treat the first word as step 1
            if len(forwards) > len(backwards): 
                forwards, backwards = backwards, forwards #switch process
            #logging.debug(f"step: {step}, forwards: {forwards}, backwords: {backwards}")

            neighbors= set()   
            for word in forwards:#visit words on this level
                if word in visited: continue

                for i in range(size):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_word = word[:i]   c   word[i 1:]
                        if next_word in backwards: return step    1 #terminating case
                        if next_word in word_set: neighbors.add(next_word)
                        #logging.debug(f"next_word{next_word}, step: {step}")
                visited.add(word) #add visited word as the final step 
            forwards = neighbors 
        #logging.debug(f"final: {step}")
        return 0
  

Ссылка на процесс переключения

         if len(forwards) > len(backwards): 
            forwards, backwards = backwards, forwards #switch process
  

Это решение краткое, но не интуитивно понятное, я попытался изменить его на

 if len(forwards) <= len(backward): current = forwards
else: current = backwards
neighbors = set()
for word in current:
 .......
  

К сожалению, последний шаг forwards = neighbors не может быть обработан должным образом.

Как можно решить проблему

это называется аглоритмом двунаправленного поиска. forward и backward в этом решении есть своего рода two-pointer идея, всегда выбирать больший набор для выполнения BFS. это помогает быстрее находить путь.

по поводу вопроса, который вы хотите использовать current вместо switch forward и backward , я думаю, что это невозможно. Причина в том, что мы используем оба forward и backward в логике, поэтому помимо current вы также должны предоставить переменную типа another . но current и another — это то же самое, что forward и backward , так что ваша идея не работает.

на мой взгляд, я думаю, что эта two-pointer версия достаточно элегантна и лаконична, и лично мне она нравится.

Я придумываю другой способ, использование current index которого близко к вашей идее:

 class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        #base case
        if (endWord not in wordList) or (not endWord) or (not beginWord) or (not wordList):
            return 0
        size = len(beginWord)
        word_set = set(wordList)    
        entries = [{beginWord}, {endWord}]
        visited = set()
        step = 0
        cur = 0
        while entries[cur] and entries[1-cur]:
            step  = 1 #treat the first word as step 1
            if entries[1-cur] > entries[cur]: #switch process
                cur ^= 1

            neighbors= set()   
            for word in entries[cur]:#visit words on this level
                if word in visited: continue

                for i in range(size):
                    for c in 'abcdefghijklmnopqrstuvwxyz':
                        next_word = word[:i]   c   word[i 1:]
                        if next_word in entries[1-cur]: return step    1 #terminating case
                        if next_word in word_set: neighbors.add(next_word)

                visited.add(word) #add visited word as the final step 
            entries[cur] = neighbors 
        return 0
  

Надеюсь, это поможет вам, и прокомментируйте, если у вас возникнут дополнительные вопросы. : )