Amazon OA 面试真题解析：Word Ladder 单词接龙与链路查找

Given a dictionary of words and a pair of words.

For the pair, display the possible word chain using the input as the starting and ending words.

Print all words in upper case, except the one letter that has changed between words.

If either word is not in the dictionary or there is no chain of words, print an appropriate error message.

Two words are connected if there is one letter that differs and the rest are the same.

For example, MALE connects to MILE (second letter, A to I), but not LIME (first and third letters are different).

Here is a sample word ladder for MALL to BENT:

MALL
BALL
BELL
BELT
BENT

For determining connected words and finding a word chain, describe the runtime for each operation in terms of number of words (N) and letters (L).

这道题本质上是经典的 Word Ladder（单词接龙）问题：给定一个词典和起始 / 结束单词，需要找出一条每次只改变一个字母的单词链，并按要求输出；如果起点或终点不在词典中，或者根本不存在可行路径，则返回错误信息。解题通常会把每个单词看成图中的节点，若两个单词只有一个位置不同就连边，然后用 BFS 搜索最短路径；在实现上可以通过逐个位置替换字符来判断邻接关系。题目还特别要求分析复杂度：判断两个单词是否相连通常是 O(L)，而搜索整条链时会与单词数量 N 和单词长度 L 相关。