110. 字符串接龙

卡码网题目链接ACM模式(opens new window)题目描述字典 strList 中从字符串 beginStr 和 endStr 的转换序列是一个按下述规格形成的序列序列中第一个字符串是 beginStr。序列中最后一个字符串是 endStr。每次转换只能改变一个位置的字符例如 ftr 可以转化 fty 但 ftr 不能转化 frx。转换过程中的中间字符串必须是字典 strList 中的字符串。beginStr 和 endStr 不在 字典 strList 中字符串中只有小写的26个字母给你两个字符串 beginStr 和 endStr 和一个字典 strList找到从 beginStr 到 endStr 的最短转换序列中的字符串数目。如果不存在这样的转换序列返回 0。输入描述第一行包含一个整数 N表示字典 strList 中的字符串数量。 第二行包含两个字符串用空格隔开分别代表 beginStr 和 endStr。 后续 N 行每行一个字符串代表 strList 中的字符串。输出描述输出一个整数代表从 beginStr 转换到 endStr 需要的最短转换序列中的字符串数量。如果不存在这样的转换序列则输出 0。输入示例6 abc def efc dbc ebc dec dfc yhn输出示例4import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); scanner.nextLine(); String beginStr scanner.next(); String endStr scanner.next(); scanner.nextLine(); ListString wordList new ArrayList(); wordList.add(beginStr); wordList.add(endStr); for (int i 0; i n; i) { wordList.add(scanner.nextLine()); } int count bfs(beginStr, endStr, wordList); System.out.println(count); } /** * 广度优先搜索-寻找最短路径 */ public static int bfs(String beginStr, String endStr, ListString wordList) { int len 1; SetString set new HashSet(wordList); SetString visited new HashSet(); QueueString q new LinkedList(); visited.add(beginStr); q.add(beginStr); q.add(null); while (!q.isEmpty()) { String node q.remove(); //上一层结束若下一层还有节点进入下一层 if (node null) { if (!q.isEmpty()) { len; q.add(null); } continue; } char[] charArray node.toCharArray(); //寻找邻接节点 for (int i 0; i charArray.length; i) { //记录旧值用于回滚修改 char old charArray[i]; for (char j a; j z; j) { charArray[i] j; String newWord new String(charArray); if (set.contains(newWord) !visited.contains(newWord)) { q.add(newWord); visited.add(newWord); //找到结尾 if (newWord.equals(endStr)) return len 1; } } charArray[i] old; } } return 0; } }