127. 单词接龙 #

问题描述#

给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：

每次转换只能改变一个字母。

转换过程中的中间单词必须是字典中的单词。

说明:

如果不存在这样的转换序列，返回 0。

所有单词具有相同的长度。

所有单词只由小写字母组成。

字典中不存在重复的单词。

你可以假设 beginWord 和 endWord 是非空的，且二者不相同。

示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出: 5

解释: 一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog",
     返回它的长度 5。
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: 0

解释: endWord "cog" 不在字典中，所以无法进行转换。

解题思路#

因为是求最短路径，所以考虑使用广度优先搜索。对于每一个单词，需要找到与它只相差一个字母的所有单词，称作它的邻居。直接的做法是使用双重循环对每两个单词进行遍历。代码如下：

from collections import defaultdict, deque
from typing import List


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def is_neighbor(w1: str, w2: str) -> bool:
            k = 0
            for i in range(len(w1)):
                if w1[i] != w2[i]:
                    k += 1
                if k > 1:
                    return False
            return True if k == 1 else False

        neighbors = defaultdict(list)
        n = len(wordList)
        for i in range(n):
            for j in range(i + 1, n):
                if is_neighbor(wordList[i], wordList[j]):
                    neighbors[wordList[i]].append(wordList[j])
                    neighbors[wordList[j]].append(wordList[i])

        steps = defaultdict(int)
        v = defaultdict(bool)

        steps[endWord] = 1
        v[endWord] = True

        q = deque([endWord])
        while q:
            word = q.popleft()
            if is_neighbor(word, beginWord):
                return steps[word] + 1

            for w in neighbors[word]:
                if not v[w]:
                    v[w] = True
                    steps[w] = steps[word] + 1
                    q.append(w)

        return 0

这里建立 neighbors 中双重循环的时间复杂度是 \(\mathcal{O}(N^2)\)，计算 is_neighbor 的最坏时间复杂度为 \(\mathcal{O}(C)\)，\(C\) 为单词的长度，所以总的时间复杂度为 \(\mathcal{O}(N^2\times C)\)。广度优先搜索过程的最坏时间复杂度为 \(\mathcal{O}(N\times\max(C,\text{avg_num_neighbors}))\)。

运行的结果是超时，但是算法思路是没有问题的，测试用例倒是显示都通过了。

上面代码主要耗时的地方在于双重循环，一个讨巧的做法是，因为单词中的字母都是小写，所以可以对每个单词的每个字母进行替换，然后观察新的单词是否在原来的单词表中。

import string
from collections import defaultdict, deque
from typing import List


class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
        def is_neighbor(w1: str, w2: str) -> bool:
            k = 0
            for i in range(len(w1)):
                if w1[i] != w2[i]:
                    k += 1
                if k > 1:
                    return False
            return True if k == 1 else False

        word_set = set(wordList)
        neighbors = defaultdict(list)
        alpha = string.ascii_lowercase
        n_chars = len(beginWord)
        for word in word_set:
            for i in range(n_chars):
                for c in alpha:
                    new_word = word[:i] + c + word[i + 1 :]
                    if new_word in word_set:
                        neighbors[word].append(new_word)
                        neighbors[new_word].append(word)

        steps = defaultdict(int)
        v = defaultdict(bool)

        steps[endWord] = 1
        v[endWord] = True

        q = deque([endWord])
        while q:
            word = q.popleft()
            if is_neighbor(word, beginWord):
                return steps[word] + 1

            for w in neighbors[word]:
                if not v[w]:
                    v[w] = True
                    steps[w] = steps[word] + 1
                    q.append(w)

        return 0

主要问题在于构建每个单词的可达邻居矩阵。

可以为每个单词创建相应的 模式结点 作为 中间结点，如 hot 对应的模式结点为 *ot, h*t, ho*，这样只要两个单词的模式结点相同，则这两个单词肯定是邻居。搜索的路径由 单词-->单词 变为了 单词-->模式结点-->单词。

为了创建 单词-->单词 的邻居矩阵，需要对 wordList 进行双重遍历（\(N\times N\)），而创建 单词-->模式结点 的邻居矩阵只需对每个单词的模式结点遍历（\(N\times C\)）。

对于测试用例：

1
2
3

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

单词-->单词 构造的邻居矩阵为：

('hot', ['dot', 'lot'])
('dot', ['hot', 'dog', 'lot'])
('lot', ['hot', 'dot', 'log'])
('dog', ['dot', 'log', 'cog'])
('log', ['dog', 'lot', 'cog'])
('cog', ['dog', 'log'])

单词-->模式结点 构造的邻居矩阵为：

('hot', ['*ot', 'h*t', 'ho*'])
('*ot', ['hot', 'dot', 'lot'])
('h*t', ['hot', 'hit'])
('ho*', ['hot'])
('dot', ['*ot', 'd*t', 'do*'])
('d*t', ['dot'])
('do*', ['dot', 'dog'])
('dog', ['*og', 'd*g', 'do*'])
('*og', ['dog', 'log', 'cog'])
('d*g', ['dog'])
('lot', ['*ot', 'l*t', 'lo*'])
('l*t', ['lot'])
('lo*', ['lot', 'log'])
('log', ['*og', 'l*g', 'lo*'])
('l*g', ['log'])
('cog', ['*og', 'c*g', 'co*'])
('c*g', ['cog'])
('co*', ['cog'])
('hit', ['*it', 'h*t', 'hi*'])
('*it', ['hit'])
('hi*', ['hit'])

添加模式结点后，寻找的路径变为了 (单词-->模式结点)-->(单词-->模式结点)-->...-->单词，所以最终得到的距离肯定是奇数，真正的距离为 \(\frac{d-1}{2}+1\)。

from typing import List
from collections import deque, defaultdict


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

        edge = defaultdict(list)

        def add_edge_word_pword(word: str):
            chars = list(word)
            for i in range(len(chars)):
                t = chars[i]
                chars[i] = "*"
                pword = "".join(chars)
                edge[word].append(pword)
                edge[pword].append(word)
                chars[i] = t

        for word in wordList:
            add_edge_word_pword(word)

        if beginWord not in edge:
            add_edge_word_pword(beginWord)

        steps = defaultdict(int)
        steps[endWord] = 1

        q = deque([endWord])
        while q:
            if steps[beginWord] != 0:
                # return (steps[beginWord] - 1) // 2 + 1
                return steps[beginWord] // 2 + 1

            word = q.popleft()
            for w in edge[word]:
                if steps[w] == 0:
                    steps[w] = steps[word] + 1
                    q.append(w)

        return 0

双向广度优先搜索。

from typing import List
from collections import deque, defaultdict


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

        edge = defaultdict(set)

        def add_edge_word_pword(word: str):
            chars = list(word)
            for i in range(len(chars)):
                t = chars[i]
                chars[i] = "*"
                pword = "".join(chars)
                edge[word].add(pword)
                edge[pword].add(word)
                chars[i] = t

        for word in wordList:
            add_edge_word_pword(word)

        if beginWord not in edge:
            add_edge_word_pword(beginWord)

        head_steps = defaultdict(int)
        tail_steps = defaultdict(int)

        head_steps[beginWord] = tail_steps[endWord] = 1

        head = deque([beginWord])
        tail = deque([endWord])

        while head and tail:
            head_word = head.popleft()
            for w in edge[head_word]:
                if tail_steps[w] != 0:
                    return (head_steps[head_word] + tail_steps[w]) // 2 + 1
                elif head_steps[w] == 0:
                    head_steps[w] = head_steps[head_word] + 1
                    head.append(w)

            tail_word = tail.popleft()
            for w in edge[tail_word]:
                if head_steps[w] != 0:
                    return (head_steps[w] + tail_steps[tail_word]) // 2 + 1
                elif tail_steps[w] == 0:
                    tail_steps[w] = tail_steps[tail_word] + 1
                    tail.append(w)

        return 0

127. 单词接龙#

问题描述#

解题思路#

127. 单词接龙 #