127. Word Ladder

127. Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word. For example,

Given: beginWord = “hit” endWord = “cog” wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”] As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5.

Note: Return 0 if there is no such transformation sequence. All words have the same length. All words contain only lowercase alphabetic characters. You may assume no duplicates in the word list. You may assume beginWord and endWord are non-empty and are not the same. UPDATE (2017/1/20): The wordList parameter had been changed to a list of strings (instead of a set of strings). Please reload the code definition to get the latest changes.

class Solution { public int ladderLength(String beginWord, String endWord, List wordList) { Set wordSet = new HashSet<>(wordList); Set visited = new HashSet<>(); visited.add(beginWord); int dist = 1; while (!visited.contains(endWord)) { Set temp = new HashSet<>(); for (String word: visited) { for (int i = 0; i < word.length(); i++) { char[] chars = word.toCharArray(); for (int j = (int)'a'; j < (int)'z' + 1; j++) { chars[i] = (char)j; String newWord = new String(chars); if (wordSet.contains(newWord)) { temp.add(newWord); wordSet.remove(newWord); } } } } dist += 1; if (temp.size() == 0) { // it nevert get to the endWord return 0; } visited = temp; } return dist; }}

class Solution { private class Node { String val; int level; Node(String val, int level) { this.val = val; this.level = level; } } public int ladderLength(String beginWord, String endWord, List wordList) { // Breadth First Search Queue queue = new LinkedList(); // put original world as a root node queue.add(new Node(beginWord, 0)); // don't check words twice Set checked = new HashSet(); while(!queue.isEmpty()) { Node word = queue.remove(); if(word.val.equals(endWord)) { return word.level + 1; } for(String w : wordList) { String key = w; if(!checked.contains(key) && isOnlyOneLetterDifference(w, word.val) ) { queue.add(new Node(w, word.level + 1)); checked.add(key); } } } return 0; } /* * validate two strings * rule: only one letter can be changed at a time */ private boolean isOnlyOneLetterDifference(String current, String destination) { // the rule: all words have the same length. if(current.length() != destination.length()) { return false; } int count = 0; for(int i=0; i < current.length(); i++) { if(current.charAt(i) != destination.charAt(i)) { count++; if(count > 1) { return false; } } } return count == 1; }}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。