Skip to content

11616: 【原1616】字符串转换序列

题目

题目描述

author: jankyee 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1616

Description

给定两个字符串(begin_str和end_str),以及一个字符串字典(字符串数组strList),找出长度最短的从begin_str到end_str的转换序列,其中转换序列需要满足以下条件:

  • 每次转换只允许改变一个字符

  • 每一个转换字符串必须存在于strList中,注意begin_str不是一个转换字符串,而end_str是一个转换字符串

Example:

给定

  • begin_str="hit"
  • end_str="cog"
  • strList = {"hot","dot","dog","lot","log","cog"}

则其中一个最短的转换序列是"hit" -> "hot" -> "dot" -> "dog" -> "cog",长度是4

Note:

  • 如果不存在满足上述条件的转换序列,返回0
  • 所有字符串长度相同
  • 所有字符都是小写字符a-z
  • 所有字符串非空
  • 输入有四行
  • 第一行是一个字符串(begin_str)
  • 第二行是一个字符串(end_str)
  • 第三行是字符串字典的长度n
  • 第四行是字符串字典(strList,n个字符串,以空格隔开)。
  • 输出有一行
  • 返回最短转换序列的长度。

Sample Input

hit
cog
6
hot dot dog lot log cog

Sample Output

4

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!