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了，可以的话，请您参考添加页面，与大家一起分享你的题解！