Replace

题目描述

你被给予两个由小写英文字母组成的字符串 $S$ 和 $T$。 Takahashi 从字符串 $S$ 开始。他可以任意次数且以任意顺序执行 $K$ 种操作中的任意一种。
第 $i$ 种操作如下：

支付代价 $1$。 然后，如果当前字符串包含字符 $C_i$，选择其一个出现并将其替换为字符串 $A_i$。 否则，什么也不做。

找到使字符串等于 $T$ 所需的最小总代价。 如果无法做到，请输出 $-1$。

输入格式

输入按照标准输入给出，格式如下： $S$ $T$ $K$ $C_1$ $A_1$ $C_2$ $A_2$ $\vdots$ $C_K$ $A_K$

输出格式

输出使字符串等于 $T$ 所需的最小总代价。 如果无法做到，请输出 $-1$。

ab
cbca
3
a b
b ca
a efg

4

a
aaaaa
2
a aa
a aaa

2

a
z
1
a abc

-1

提示

$1\leq |S|\leq |T|\leq 50$ $1\leq K\leq 50$ $C_i$ 是 $a$、$b$、$\ldots$ 或 $z$。 $1\leq |A_i|\leq 50$ $S$、$T$ 和 $A_i$ 都是由小写英文字母组成的字符串。 将 $C_i$ 视为长度为 $1$ 的字符串时，$C_i\neq A_i$。 所有对 $(C_i,A_i)$ 都是互不相同的。从 $S=$$ab$ 开始，Takahashi 可以通过如下四次操作得到 $T=$$cbca$：

将 $ab$ 中的第 $1$ 个字符 $a$ 替换为 $b$（第 $1$ 种操作）。字符串变为 $bb$。 将 $bb$ 中的第 $2$ 个字符 $b$ 替换为 $ca$（第 $2$ 种操作）。字符串变为 $bca$。 将 $bca$ 中的第 $1$ 个字符 $b$ 替换为 $ca$（第 $2$ 种操作）。字符串变为 $caca$。 将 $caca$ 中的第 $2$ 个字符 $a$ 替换为 $b$（第 $1$ 种操作）。字符串变为 $cbca$。

每次操作的代价为 $1$，总共为 $4$，这是最小可能值。
两次操作 $a$ $\to$ $aaa$ $\to$ $aaaaa$ 的代价为 $2$，这也是最小可能值。
没有任何操作序列可以把 $S=$$a$ 变为 $T=$$z$。

标签: AtCoder|abc261G

来源

AtCoder|abc261G