首页 > 代码库 > [LeetCode]127 Word Ladder
[LeetCode]127 Word Ladder
https://oj.leetcode.com/problems/word-ladder/
http://blog.csdn.net/linhuanmars/article/category/1918893/2
public class Solution { public int ladderLength(String start, String end, Set<String> dict) { // Put end into dict Set<String> dictionary = new HashSet<>(dict); dictionary.add(end); Set<String> visited = new HashSet<>(); // BFS int nextlevel = 0; int curlevel = 1; int result = 1; Queue<String> queue = new LinkedList<>(); queue.offer(start); visited.add(start); while (!queue.isEmpty()) { String node = queue.poll(); if (node.equals(end)) return result; curlevel --; Set<String> nextstrs = findnext(node, dictionary, visited); for (String nextstr : nextstrs) { queue.offer(nextstr); } nextlevel += nextstrs.size(); if (curlevel == 0) { // This level is finished curlevel = nextlevel; nextlevel = 0; result ++; } } return 0; } // Given string, find next str from dict (excluding visited) private Set<String> findnext(String from, Set<String> dict, Set<String> visited) { Set<String> toReturn = new HashSet<>(); char[] chars = from.toCharArray(); for (int i = 0 ; i < chars.length ; i ++) { char originalc = chars[i]; for (char j = ‘a‘ ; j <= ‘z‘ ; j ++) { if (originalc == j) continue; chars[i] = j; String str = new String(chars); if (dict.contains(str) && !visited.contains(str)) { toReturn.add(str); // NOTE // Pre put str into visited, because we will anyway visited // This is to increase latency. visited.add(str); } } // NOTE // Don‘t forget change it back. chars[i] = originalc; } return toReturn; } }
[LeetCode]127 Word Ladder
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。