AT_abc261_g [ABC261G] Replace

题目描述

给定两个仅由小写英文字母组成的字符串 $S$ 和 $T$。

高桥君从字符串 $S$ 开始，可以任意多次重复选择以下 $K$ 种操作中的一种进行操作。
第 $i$ 种操作的形式如下：

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

请你求出将字符串 $S$ 变为与 $T$ 完全相同所需的最小总代价。如果无法变为 $T$，则输出 $-1$。

输入格式

输入以如下格式从标准输入读入。

$S$ $T$
$K$
$C_1$ $A_1$
$C_2$ $A_2$
$\vdots$
$C_K$ $A_K$

输出格式

输出将 $S$ 变为 $T$ 所需的最小总代价。如果无法变为 $T$，则输出 $-1$。

输入输出样例 #1

输入 #1

ab
cbca
3
a b
b ca
a efg

输出 #1

4

输入输出样例 #2

输入 #2

a
aaaaa
2
a aa
a aaa

输出 #2

2

输入输出样例 #3

输入 #3

a
z
1
a abc

输出 #3

-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)$ 均不同

样例解释 1

高桥君从 $S=$ab 开始，可以通过如下 $4$ 次操作将其变为 $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$，且这是最小值。

样例解释 2

a \to aaa \to aaaaa，总代价为 $2$，且这是最小值。

样例解释 3

无论如何操作，都无法将 $S=$a 变为 $T=$z。

由 ChatGPT 4.1 翻译