第122题:基因串
题目描述:基因串是由一串有限长度的基因所组成的,其中每一个基因都可以用26个英文大写字母中的一个来表示,不同的字母表示不同的基因类型。一个单独的基因可以生长成为一对新的基因,而可能成长的规则是通过一个有限的成长规则集所决定的。每一个成长的规则可以用三个大写英文字母A1A2A3来描述,这个规则的意思是基因A1可以成长为一对基因A2A3。
用大写字母S来表示一类称作超级基因的基因,因为每一个基因串都是由一串超级基因根据给出的规则所成长出来的。
给你若干成长的规则和一个目标基因串,对于每个基因串,请你判断它是否可以由一个有限长度的超级基因串成长得出。如果可以,输出可成长为该基因串的最短超级基因串的长度,否则输出-1。
成长规则存储在列表L中, 目标基因串为dest。例如:
L=["BCA","ABC","SAB"], dest="BCCA", 则输出1。 Note:S->AB->BCB->BCCA
示例:输入:L = ["BCA", "ABC", "SAB"]
dest = "BCCA"
输出:1