LeetCode 题解（94）: Word Ladder

本文主要是介绍LeetCode 题解（94）: Word Ladder，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：

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

1. Only one letter can be changed at a time
2. Each intermediate word must exist in the dictionary

For example,

Given:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]

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.

题解：

用BFS + 单Queue + 每次与wordDict比较，C++可以刚刚通过时间测试，java不能通过时间测试。于是网上学来BFS + 双Queue + 每次修改一个字符并与wordDict比较，每次止血比较 stringLength * 26次。

C++版：

class Solution {
public:int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {if(beginWord == endWord)return 2;if(wordDict.empty())return 0;wordDict.insert(endWord);queue<pair<string, int>> forward;forward.push(pair<string, int>(beginWord, 1));if(wordDict.find(beginWord) != wordDict.end())wordDict.erase(beginWord);while(!forward.empty()) {pair<string, int> front = forward.front();forward.pop();if(front.first == endWord)return front.second;for(unordered_set<string>::iterator iter = wordDict.begin(); iter != wordDict.end(); ) {if(distance(*iter, front.first)) {forward.push(pair<string, int>(*iter, front.second+1));wordDict.erase(iter++);} else {iter++;}}cout << endl;}return 0;}bool distance(const string& a, const string& b) {int diff = 0;for(unsigned int i = 0; i < a.length(); i++) {if(a[i] != b[i])diff++;if(diff > 1)return false;}if(diff == 1)return true;elsereturn false;}
};

Java版：

注意String比较的时候要用.equals()

public class Solution {public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {if(beginWord == null || endWord == null || wordDict.size() == 0)return 0;Queue<String> queue1 = new LinkedList<>();Queue<String> queue2 = new LinkedList<>();queue1.add(beginWord);int distance = 1;while(wordDict.size() != 0 && queue1.size() != 0) {while(queue1.size() != 0) {String current = queue1.poll();for(int i = 0; i < current.length(); i++) {for(char j = 'a'; j <= 'z'; j++) {String temp = current;if(current.charAt(i) == j)continue;StringBuilder newString = new StringBuilder(current);newString.setCharAt(i, j);current = newString.toString();if(current.equals(endWord))return distance + 1;if(wordDict.contains(current)) {queue2.add(current);wordDict.remove(current);}current = temp;}}}distance += 1;queue1.addAll(queue2);queue2.clear();}return 0;}
}

Python版：

注意复制deque的时候要用深copy。import copy

a = copy.copy(b)

from collections import dequeclass Solution:# @param beginWord, a string# @param endWord, a string# @param wordDict, a set<string># @return an integerdef ladderLength(self, beginWord, endWord, wordDict):if beginWord == None or endWord == None or len(wordDict) == 0:return 0q1 = deque()q1.append(beginWord)q2 = deque()distance = 1while len(wordDict) != 0 and len(q1) != 0:while len(q1) != 0:current = q1.pop()for i in range(len(current)):temp = currentfor j in "abcdefghijklmnopqrstuvwxyz":if j == i:continuecurrent = current[0:i] + j + current[i+1:]if current == endWord:return distance + 1if current in wordDict:q2.append(current)wordDict.remove(current)current = tempdistance += 1q1 = copy.copy(q2)q2.clear()return 0

这篇关于LeetCode 题解（94）: Word Ladder的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---