算法题--单词搭桥

image.png

0. 链接

题目链接

1. 题目

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time.
Each transformed word must exist in the word list.
Note:

Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.
You may assume no duplicates in the word list.
You may assume beginWord and endWord are non-empty and are not the same.
Example 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.

Example 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.

2. 思路1: 双向BFS

• 基本思路是分别从beginWord和endWord开始, 各自按照BFS的原则, 构建路径, 直到两个方向在中间相遇
• 时间复杂度 O(M*N), 其中M为每个单词的长度, N为单词个数
• 空间复杂度 O(M * N)

3. 代码

# coding:utf8
from typing import List
import collections


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

    def visit_word_node(self, queue, visited, other_visited):
        cur_word, level = queue.popleft()
        for i in range(self.length):
            inter_word = cur_word[:i] + '*' + cur_word[i + 1:]
            for word in self.all_combo_dict[inter_word]:
                if word in other_visited:
                    return level + other_visited[word]
                if word not in visited:
                    visited[word] = level + 1
                    queue.append((word, level + 1))
        return None

    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        if endWord not in wordList or not beginWord or not endWord or not wordList:
            return 0

        self.length = len(beginWord)
        for word in wordList:
            for i in range(self.length):
                key = word[:i] + '*' + word[i + 1:]
                self.all_combo_dict[key].append(word)

        queue_begin = collections.deque([(beginWord, 1)])
        queue_end = collections.deque([(endWord, 1)])

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

        while queue_begin and queue_end:
            ans = self.visit_word_node(queue_begin, visited_begin, visited_end)
            if ans:
                break
            ans = self.visit_word_node(queue_end, visited_end, visited_begin)
            if ans:
                break

        return ans if ans is not None else 0


def my_test(solution, beginWord, endWord, wordList):
    print('input:')
    print('\tbeginWord={}, endWord={}, wordList={}'.format(beginWord, endWord, wordList))
    print('output:{}'.format(solution.ladderLength(beginWord, endWord, wordList)))
    print('=' * 50)


solution = Solution()
my_test(solution, 'hit', 'cog', ['hot', 'dot', 'dog', 'lot', 'log', 'cog'])
solution = Solution1()
my_test(solution, 'hit', 'cog', ["hot","dot","dog","lot","log"])
solution = Solution1()
my_test(solution, 'hot', 'dog', ['hot', 'dog'])
solution = Solution1()
my_test(solution, "hit", "cog", ["hot", "dot", "tog", "cog"])

输出结果

input:
    beginWord=hit, endWord=cog, wordList=['hot', 'dot', 'dog', 'lot', 'log', 'cog']
output:5
==================================================
input:
    beginWord=hit, endWord=cog, wordList=['hot', 'dot', 'dog', 'lot', 'log']
output:0
==================================================
input:
    beginWord=hot, endWord=dog, wordList=['hot', 'dog']
output:0
==================================================
input:
    beginWord=hit, endWord=cog, wordList=['hot', 'dot', 'tog', 'cog']
output:0
==================================================

4. 结果

image.png