问题1399--相似的单词

1399: 相似的单词

时间限制: 1 Sec  内存限制: 128 MB
提交: 215  解决: 106
[状态] [讨论版] [提交] [命题人:]
题目描述

两个单词的组成字母一样,相应的字母数量也一样,则称这两个单词是相似的。比如dog和god是相似的。现在给两个单词,要让它们成为相似单词,怎么办呢?比如dog和good要相似,good删除一个'o'嘛...好简单。
我们可以进行一系列操作,一次操作是删除一个单词的一个字母。现在我想知道两个单词要相似最少经过几步的操作,可以吗?

输入

首先输入一个整数T(0<T<=10),表示有T个测试实例。每个测试实例包含两个单词,每个单词的长度小于等于1000。 单词中只包含英文小写字母。

输出

输出最少经过几步的操作可以使两个单词成为相似单词。每个输出占一行。

样例输入 Copy
2
dog
god
dog
good
样例输出 Copy
0
1
来源/分类