Word Ladder
Medium
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.
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.
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.Analysis
这道题很经典，巧妙之处在于转化问题：wordList中的word相当于图中的节点，是否存在边连接节点呢？就在于改变word中的一个字符时能否找到另一个节点，即图中的两个word节点之间否有边，取决于两个word之间是否只相差一个字符串。beginWord相当于起点，endWord相当于终点。Word Ladder的问题本质其实就是寻找起点到终点的最短路径。这样，用BFS就可以解决。
改变字符串中的字符的两种方法：
StringBuilder()
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(j, ch);
String newWord = sb.toString();
...
}toCharArray()
char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
chs[i] = ch;
String newStr = new String(chs);
...
}The intuition:
BFS -- Altering one character at a time for beginWord, and see if it's in the wordList, if yes, then add to the toSearch list; for the word in toSearch list, do the same: altering one character at a time, see if it's in wordList, so on and so forth.
Note: to avoid cyclical search, we need to remove the "searched" word from the wordList
Optimization: using two end BFS
Solution
BFS (using set)- (133ms 43.15%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
// wordSet storing non-visited words
Set<String> wordSet = new HashSet<String> (wordList);
// reachSet storing visted words
Set<String> reachSet = new HashSet<String>();
if (beginWord == null || endWord == null || !wordSet.contains(endWord)) return 0;
reachSet.add(beginWord);
int step = 1;
while (!reachSet.contains(endWord)) {
HashSet<String> temp = new HashSet<String>();
for (String s : reachSet) {
for (int i = 0; i < s.length(); i++) {
char[] chs = s.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++ ) {
chs[i] = ch;
String nStr = new String(chs);
if (wordSet.contains(nStr)) {
if (endWord.equals(nStr)) return step + 1;
// add new valid word to the temp set
temp.add(nStr);
wordSet.remove(nStr);
}
}
}
}
step++;
if (temp.size() == 0) return 0;
reachSet = temp;
}
return step;
}
}A more "traditional" BFS using Queue (63 ms, faster than 78.37%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>(wordList);
if (!set.contains(endWord)) {
return 0;
}
Deque<String> q = new ArrayDeque<>();
q.offer(beginWord);
int step = 1;
while (!q.isEmpty()) {
int size = q.size();
for (int i = 0; i < size; i++) {
String word = q.poll();
int wordLength = word.length();
for (int j = 0; j < wordLength; j++) {
StringBuilder sb = new StringBuilder(word);
for (char ch = 'a'; ch <= 'z'; ch++) {
sb.setCharAt(j, ch);
String newWord = sb.toString();
if (newWord.equals(endWord)) {
return step + 1;
}
if (set.contains(newWord)) {
q.offer(newWord);
set.remove(newWord); // to avoid infinited loop
}
}
}
}
step++;
}
return 0;
}
}Two-End BFS (15 ms, faster than 99.01%)
class Solution {
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
Set<String> set = new HashSet<>();
for(String str : wordList) set.add(str);
if (beginWord == null || endWord == null || !set.contains(endWord)) return 0;
Set<String> beginSet = new HashSet<>();
Set<String> endSet = new HashSet<>();
beginSet.add(beginWord);
endSet.add(endWord);
set.remove(endWord);
int step = 1;
while(!beginSet.isEmpty() && !endSet.isEmpty()) {
Set<String> next = new HashSet<>();
if (beginSet.size() > endSet.size()) {
Set<String> temp = beginSet;
beginSet = endSet;
endSet = temp;
}
for(String str : beginSet) {
char[] word = str.toCharArray();
for(int i = 0; i < word.length; i++) {
char old_c = word[i];
for(char c = 'a'; c <= 'z'; c++) {
word[i] = c;
String cur = new String(word);
if (endSet.contains(cur)) return step+1;
if (set.contains(cur)) {
next.add(cur);
set.remove(cur);
}
}
word[i] = old_c;
}
}
beginSet = next;
step++;
}
return 0;
}
}Reference
Last updated
Was this helpful?