Word Ladder

题目描述

你得到两个由小写英文字母组成的字符串 $S$ 和 $T$ 。这里， $S$ 和 $T$ 的长度相等。令 $X$ 为一个空数组，重复以下操作直到 $S$ 等于 $T$ ：

改变 $S$ 中的一个字符，并将 $S$ 附加到 $X$ 的末尾。

找到以这种方式得到的具有最少元素个数的字符串数组 $X$ 。如果存在多个具有最小元素个数的数组，请在它们中找到字典序最小的一个。

什么是字符串数组的字典序？

一个长度为 $N$ 的字符串 $S = S_1 S_2 \ldots S_N$ 当且仅当存在整数 $1 \leq i \leq N$ 满足以下两项时，被称为在字典序上小于字符串 $T = T_1 T_2 \ldots T_N$：

$S_1 S_2 \ldots S_{i-1} = T_1 T_2 \ldots T_{i-1}$ $S_i$ 在字母表中出现在 $T_i$ 之前。

一个有 $M$ 个元素的字符串数组 $X = (X_1,X_2,\ldots,X_M)$ 在字典序上小于另一个有 $M$ 个元素的字符串数组 $Y = (Y_1,Y_2,\ldots,Y_M)$ 当且仅当存在整数 $1 \leq j \leq M$ 满足以下两项：

$(X_1,X_2,\ldots,X_{j-1}) = (Y_1,Y_2,\ldots,Y_{j-1})$ $X_j$ 在字典序上小于 $Y_j$ 。

输入从标准输入给出，格式如下： $S$ $T$

令 $M$ 为所需数组的元素个数。输出 $M + 1$ 行。第一行应包含值 $M$ 。第 $i + 1$ 行 $(1 \leq i \leq M)$ 应包含数组的第 $i$ 个元素。

adbe
bcbc

3
acbe
acbc
bcbc

abcde
abcde

afwgebrw
oarbrenq

8
aawgebrw
aargebrw
aarbebrw
aarbebnw
aarbebnq
aarbeenq
aarbrenq
oarbrenq

$S$ 和 $T$ 是由小写英文字母组成的字符串，长度在 $1$ 到 $100$ （含）之间。 $S$ 和 $T$ 的长度相等。最初， $S =$ $adbe$ 。我们可以通过执行以下操作得到 $X = ($ $acbe$ $,$ $acbc$ $,$ $bcbc$ $)$ ：

将 $S$ 变为 $acbe$ 并将 $acbe$ 附加到 $X$ 的末尾。

将 $S$ 变为 $acbc$ 并将 $acbc$ 附加到 $X$ 的末尾。

将 $S$ 变为 $bcbc$ 并将 $bcbc$ 附加到 $X$ 的末尾。

标签: AtCoder|abc370C

AtCoder|abc370C