又写一道好老好老的题。第一次见到是。。。。四年前了吧，老得我都觉得自己没啥长进了。
正能量正能量！
Example 1:
Input: beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”, return its length 5. Example 2:
Input: beginWord = “hit” endWord = “cog” wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.
双向广度优先搜索，同时从起点和终点搜索。 Runtime: 61 ms, faster than 54.54% of Java online submissions for Word Ladder. 试了一下 ，并不比单向快，不知道哪有问题不。
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(wordList.indexOf(endWord) == -1) return 0; int length = 0; HashSet<String> set = new HashSet<String>(); for(String s: wordList){ set.add(s); } Queue<String> qStart = new LinkedList<String>(); qStart.offer(beginWord); Queue<String> qEnd = new LinkedList<String>(); qEnd.offer(endWord); while(!qStart.isEmpty() || !qEnd.isEmpty()){ length++; int size = qStart.size(); for(int i = 0; i < size; i++){ String str = qStart.poll(); for(int j = 0; j < str.length(); j++){ char[] chars = str.toCharArray(); for(char c = 'a'; c < 'z'; c++){ chars[j] = c; String newString = String.valueOf(chars); if(qEnd.contains(newString)) return length + 1; if(set.contains(newString)){ qStart.offer(newString); set.remove(newString); } } } } Queue<String> temp = new LinkedList<String>(); temp = qStart; qStart = qEnd; qEnd = temp; } return 0; } }图转自花花酱
单向广度。 速度还是可以的。 Runtime: 45 ms, faster than 82.10% of Java online submissions for Word Ladder.
class Solution { public int ladderLength(String beginWord, String endWord, List<String> wordList) { if(wordList.indexOf(endWord) == -1) return 0; int length = 1; HashSet<String> set = new HashSet<String>(); for(String s: wordList){ set.add(s); } Queue<String> q = new LinkedList<String>(); q.offer(beginWord); while(!q.isEmpty()){ length++; int size = q.size(); for(int i = 0; i < size; i++){ String str = q.poll(); for(int j = 0; j < str.length(); j++){ char[] chars = str.toCharArray(); for(char c = 'a'; c < 'z'; c++){ chars[j] = c; String newString = String.valueOf(chars); if(newString.equals(endWord)) return length; if(set.contains(newString)){ q.offer(newString); set.remove(newString); } } } } } return 0; } }总结
用set，否则的话，TimeExceedingLimit！用queue的话，先把size算出来int size = q.size();，要不得size不变了吗for(char c = ‘a’; c < ‘z’; c++)遍历，set.remove(newString); 遍历过的remove掉