题目描述

(大致翻译来自 《训练指南》)

给定两个长度相等，只有小写字母组成的字符串s和t(s与t长度相等)，每步可以把s的一个连续子串"刷"成同一个字母，问至少需要多少步，才能把s变成t?

例如s=bbbbbbb，t=aaabccb，则最少需要两步可以将s变成t 。(见解释)

输入格式

两个字符串，s，t，如题面所说。保证输入的s与t长度相等

输出格式

一个整数 表示s变成t所需的最少步数

样例

####样例输入

bbbbbbb
aaabccb

####样例输出

2

####样例解释

bbbbbbb->aaabbbb->aaabccb

数据范围与提示

1<= 字符串长度 <= 300，两个字符串长度保证相等