72. 字串变换

单点时限: 10.0 sec

内存限制: 512 MB

假设对一个字符串可进行以下两种类型的变换:

  1. 对字串中的任意一个字符进行复制。例如:xyz 复制其中一个字符 y 变为 xyyz
  2. 对字串中的相邻的两个相同字符删除其中一个。例如:xxyz 删除其中一个字符 x 变为 xyz

现在给出 个字符串,计算最少需要几次以上变换才能使得这 个字符串都变得相同。

输入格式

第一行输入一个整数

接下来 行,每行输入一个字符串,由小写字母组成,字符串长度不超过

  • 对于 的数据,
  • 对于 的数据,

输出格式

在每一行中输出所需要的最小变换次数。如果不可能达成目标,则输出

样例

Input
2
abc
bac
Output
-1
Input
3
aaabbb
ab
aabb
Output
4
Input
3
aabbcc
aabbcc
aabbcc
Output
0

提示

例如:有 3 个字串 aaabbbabaabb,需要最少 次变换,最后全部变成 aabb

145 人解决,274 人已尝试。

264 份提交通过,共有 2197 份提交。

4.5 EMB 奖励。

创建: 2 年前.

修改: 1 年,1 月前.

最后提交: 58 分钟前.

来源: 2018 实训第一次机考

题目标签