#101. 字串变换
字串变换
题目描述
已知有两个字串 及一组字串变换的规则(至多个规则):
…
规则的含义为:在 中的子串 可以变换为 、 可以变换为 …
。
例如:
变换规则为:
则此时, 可以经过一系列的变换变为,其变换的过程为:
共进行了三次变换,使得 变换为。
输入格式
输入格式如下:
|-> 变换规则 … … /
所有字符串长度的上限为。
输出格式
若在 步(包含步)以内能将变换为 ,则输出最少的变换步数;否则输出
已知有两个字串 A,B 及一组字串变换的规则(至多6个规则):
A1−>B1
A2−>B2
…
规则的含义为:在 A 中的子串 A1 可以变换为 B1、A2 可以变换为 B2 …
。
例如:A=’abcd’ B=’xyz’
变换规则为:
‘abc’−>‘xu’ ‘ud’−>‘y’ ‘y’−>‘yz’
则此时,A 可以经过一系列的变换变为B,其变换的过程为:
‘abcd’−>‘xud’−>‘xy’−>‘xyz’
共进行了三次变换,使得A 变换为B。
输入格式如下:
A B
A1 B1
A2 B2
|-> 变换规则 … … /
所有字符串长度的上限为20。
若在 10 步(包含10步)以内能将A变换为B ,则输出最少的变换步数;否则输出”NOANSWER!”
abcd xyz
abc xu
ud y
y yz
3