[leetcode] Word Ladder

直接BFS..... 有一处搞了很久 发现原来return是转换过程有多少个word... 而不是换了多少个字母

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45

public class Solution { public int ladderLength(String beginWord, String endWord, Set<String> wordList) { HashSet<String> notVisited = new HashSet<String>(wordList); boolean found = false; HashSet<String> nextLevel = new HashSet<String>(); HashSet<String> curLevel = new HashSet<String>(); curLevel.add(beginWord); notVisited.remove(beginWord); int level = 1; while (!found && !curLevel.isEmpty()){ if (curLevel.contains(endWord)){ found = true; }else{ level++; } for (String cur:curLevel){ getNextWords(nextLevel, notVisited, cur); } HashSet<String> inter = nextLevel; nextLevel = curLevel; curLevel = inter; nextLevel.clear(); } return found?level:0; } public void getNextWords(HashSet<String> nextWord, HashSet<String>notVisited, String current){ char []possible = current.toCharArray(); for (int i = 0; i < possible.length; i++){ char origin = possible[i]; for (char a = 'a'; a <= 'z'; a++){ if (a != origin){ possible[i] = a; String temp = String.valueOf(possible); if (notVisited.contains(temp)){ nextWord.add(temp); notVisited.remove(temp); } } } possible[i] = origin; } } }