首页 > 代码库 > [LeetCode]126 Word Ladder II
[LeetCode]126 Word Ladder II
https://oj.leetcode.com/problems/word-ladder-ii/
http://blog.csdn.net/linhuanmars/article/details/23071455
public class Solution { public List<List<String>> findLadders(String start, String end, Set<String> dict) { List<List<String>> toReturn = new ArrayList<>(); Queue<Node> queue = new LinkedList<>(); queue.offer(new Node(start, new ArrayList<String>())); int minlen = -1; Set<String> visited = new HashSet<>(); visited.add(start); while (!queue.isEmpty()) { Node node = queue.poll(); if (node.str.equals(end)) { if (minlen == -1) { toReturn.add(node.path); minlen = node.path.size(); } else if (node.path.size() == minlen) { toReturn.add(node.path); } } else { visited.add(node.str); List<Node> nextnodes = next(node, dict, visited); for (Node nextnode : nextnodes) queue.offer(nextnode); } } return toReturn; } private List<Node> next(Node from, Set<String> dict, Set<String> visited) { List<Node> toReturn = new ArrayList<>(); char[] chars = from.str.toCharArray(); for (int i = 0 ; i < chars.length ; i ++) { char oric = chars[i]; for (char c = ‘a‘ ; c <= ‘z‘ ; c ++) { if (c == oric) continue; chars[i] = c; String str = new String(chars); if (dict.contains(str) && !visited.contains(str)) { toReturn.add(new Node(str, from.path)); } } chars[i] = oric; } return toReturn; } private static class Node { String str; List<String> path; Node(String str, List<String> oldpath) { this.str = str; path = new ArrayList<>(oldpath); path.add(str); } } }
[LeetCode]126 Word Ladder II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。