127. Word Ladder

  • 19.2%

https://leetcode.com/problems/word-ladder/#/description

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:

  1. Only one letter can be changed at a time.
  2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.
1
2
3
4
5
6
7
8
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.


https://discuss.leetcode.com/topic/16983/easy-76ms-c-solution-using-bfs

Easy 76ms C++ Solution using BFS

Well, this problem has a nice BFS structure.

Let’s see the example in the problem statement.

1
2
3
4
5
start = "hit"

end = "cog"

dict = ["hot", "dot", "dog", "lot", "log"]

Since only one letter can be changed at a time, if we start from “hit”, we can only change to those words which have only one different letter from it, like “hot”. Putting in graph-theoretic terms, we can say that “hot” is a neighbor of “hit”.

The idea is simpy to begin from start, then visit its neighbors, then the non-visited neighbors of its neighbors… Well, this is just the typical BFS structure.

To simplify the problem, we insert end into dict. Once we meet end during the BFS, we know we have found the answer. We maintain a variable dist for the current distance of the transformation and update it by dist++ after we finish a round of BFS search (note that it should fit the definition of the distance in the problem statement). Also, to avoid visiting a word for more than once, we erase it from dict once it is visited.

The code is as follows.

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
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
wordDict.insert(endWord);
queue<string> toVisit;
addNextWords(beginWord, wordDict, toVisit);
int dist = 2;
while (!toVisit.empty()) {
int num = toVisit.size();
for (int i = 0; i < num; i++) {
string word = toVisit.front();
toVisit.pop();
if (word == endWord) return dist;
addNextWords(word, wordDict, toVisit);
}
dist++;
}
}
private:
void addNextWords(string word, unordered_set<string>& wordDict, queue<string>& toVisit) {
wordDict.erase(word);
for (int p = 0; p < (int)word.length(); p++) {
char letter = word[p];
for (int k = 0; k < 26; k++) {
word[p] = 'a' + k;
if (wordDict.find(word) != wordDict.end()) {
toVisit.push(word);
wordDict.erase(word);
}
}
word[p] = letter;
}
}
};

The above code can still be speeded up if we also begin from end. Once we meet the same word from start and end, we know we are done. This link provides a nice two-end search solution. I rewrite the code below for better readability. Note that the use of two pointers phead and ptail save a lot of time. At each round of BFS, depending on the relative size of head and tail, we point phead to the smaller set to reduce the running time.

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
class Solution {
public:
int ladderLength(string beginWord, string endWord, unordered_set<string>& wordDict) {
unordered_set<string> head, tail, *phead, *ptail;
head.insert(beginWord);
tail.insert(endWord);
int dist = 2;
while (!head.empty() && !tail.empty()) {
if (head.size() < tail.size()) {
phead = &head;
ptail = &tail;
}
else {
phead = &tail;
ptail = &head;
}
unordered_set<string> temp;
for (auto itr = phead -> begin(); itr != phead -> end(); itr++) {
string word = *itr;
wordDict.erase(word);
for (int p = 0; p < (int)word.length(); p++) {
char letter = word[p];
for (int k = 0; k < 26; k++) {
word[p] = 'a' + k;
if (ptail -> find(word) != ptail -> end())
return dist;
if (wordDict.find(word) != wordDict.end()) {
temp.insert(word);
wordDict.erase(word);
}
}
word[p] = letter;
}
}
dist++;
swap(*phead, temp);
}
return 0;
}
};

https://discuss.leetcode.com/topic/10372/share-my-two-end-bfs-in-c-80ms

Share my two-end BFS in C++ 80ms.

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
//BFS, two-end method
//traverse the path simultaneously from start node and end node, and merge in the middle
//the speed will increase (logN/2)^2 times compared with one-end method
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_set<string> begSet, endSet, *set1, *set2;
begSet.insert(start);
endSet.insert(end);
int h=1, K=start.size();
while(!begSet.empty()&&!endSet.empty()){
if(begSet.size()<=endSet.size()){ //Make the size of two sets close for optimization
set1=&begSet; //set1 is the forward set
set2=&endSet; //set2 provides the target node for set1 to search
}
else{
set1=&endSet;
set2=&begSet;
}
unordered_set<string> itmSet; //intermediate Set
h++;
for(auto i=set1->begin();i!=set1->end();i++){
string cur=*i;
for(int k=0;k<K;k++){ //iterate the characters in string cur
char temp=cur[k];
for(int l=0;l<26;l++){ //try all 26 alphabets
cur[k]='a'+l;
auto f=set2->find(cur);
if(f!=set2->end())return h;
f=dict.find(cur);
if(f!=dict.end()){
itmSet.insert(cur);
dict.erase(f);
}
}
cur[k]=temp;
}
}
swap(*set1, itmSet);
}
return 0;
}

https://discuss.leetcode.com/topic/43246/simple-to-understand-python-solution-using-list-preprocessing-and-bfs-beats-95

Simple to understand Python solution using list preprocessing and BFS, beats 95%

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
from collections import deque


class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):

def construct_dict(word_list):
d = {}
for word in word_list:
for i in range(len(word)):
s = word[:i] + "_" + word[i+1:]
d[s] = d.get(s, []) + [word]
return d

def bfs_words(begin, end, dict_words):
queue, visited = deque([(begin, 1)]), set()
while queue:
word, steps = queue.popleft()
if word not in visited:
visited.add(word)
if word == end:
return steps
for i in range(len(word)):
s = word[:i] + "_" + word[i+1:]
neigh_words = dict_words.get(s, [])
for neigh in neigh_words:
if neigh not in visited:
queue.append((neigh, steps + 1))
return 0

d = construct_dict(wordList | set([beginWord, endWord]))
return bfs_words(beginWord, endWord, d)

https://discuss.leetcode.com/topic/42623/compact-python-solution

Compact Python solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
wordList.add(endWord)
queue = collections.deque([[beginWord, 1]])
while queue:
word, length = queue.popleft()
if word == endWord:
return length
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i+1:]
if next_word in wordList:
wordList.remove(next_word)
queue.append([next_word, length + 1])
return 0

172ms, 78.99%, June.24th, 2016

https://leetcode.com/discuss/48083/share-python-solutions-concise-160ms-optimized-solution-100ms

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
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: Set[str]
:rtype: int
"""
length = 2
front, back = set([beginWord]), set([endWord])
wordList.discard(beginWord)
while front:
# generate all valid transformations
front = wordList & (set(word[:index] + ch + word[index+1:] for word in front
for index in range(len(beginWord)) for ch in 'abcdefghijklmnopqrstuvwxyz'))
if front & back:
# there are common elements in front and back, done
return length
length += 1
if len(front) > len(back):
# swap front and back for better performance (fewer choices in generating nextSet)
front, back = back, front
# remove transformations from wordList to avoid cycle
wordList -= front
return 0

https://discuss.leetcode.com/topic/20965/java-solution-using-dijkstra-s-algorithm-with-explanation

Java Solution using Dijkstra’s algorithm, with explanation

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
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
Set<String> reached = new HashSet<String>();
reached.add(beginWord);
wordDict.add(endWord);
int distance = 1;
while (!reached.contains(endWord)) {
Set<String> toAdd = new HashSet<String>();
for (String each : reached) {
for (int i = 0; i < each.length(); i++) {
char[] chars = each.toCharArray();
for (char ch = 'a'; ch <= 'z'; ch++) {
chars[i] = ch;
String word = new String(chars);
if (wordDict.contains(word)) {
toAdd.add(word);
wordDict.remove(word);
}
}
}
}
distance++;
if (toAdd.size() == 0) return 0;
reached = toAdd;
}
return distance;
}

Basically I keep two sets of words, one set reached that represents the borders that have been reached with “distance” steps; another set wordDict that has not been reached. In the while loop, for each word in the reached set, I give all variations and check if it matches anything from wordDict, if it has a match, I add that word into toAdd set, which will be my “reached” set in the next loop, and remove the word from wordDict because I already reached it in this step. And at the end of while loop, I check the size of toAdd, which means that if I can’t reach any new String from wordDict, I won’t be able to reach the endWord, then just return 0. Finally if the endWord is in reached set, I return the current steps “distance”.

The idea is that reached always contain only the ones we just reached in the last step, and wordDict always contain the ones that haven’t been reached. This is pretty much what Dijkstra’s algorithm does, or you can see this as some variation of BFS.

ps: I get TLE at the first two submissions, because when I check if wordDict has any matches with reached set, I use two for loops and determine if any pair of words differ by one. That’s a huge slow-down because it’ll takes m (size of reached) n (size of wordDict) l (length of words) time, while in this solution, it takes 26 l m time. So when n is huge, this solution will be (n/26) times faster.

https://discuss.leetcode.com/topic/20965/java-solution-using-dijkstra-s-algorithm-with-explanation/2

I think we can use a queue to replace the reached set, by which we can avoid duplicate check?

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
public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Queue<String> queue = new LinkedList<>();
queue.offer(beginWord);
wordList.add(endWord);
wordList.remove(beginWord);
int level = 1;
while(!queue.isEmpty()){
int size = queue.size();
for(int i=0;i<size;i++){
String str = queue.poll();
if(str.equals(endWord))return level;
for(String neighbor : neighbors(str,wordList)){
queue.offer(neighbor);
}
}
level++;
}
return 0;
}

public List<String> neighbors(String s, Set<String> wordList){
List<String> res = new LinkedList<>();
for(int i=0;i<s.length();i++){
char [] chars = s.toCharArray();
for(char ch = 'a'; ch <= 'z'; ch++){
chars[i] = ch;
String word = new String(chars);
if(wordList.remove(word)){
res.add(word);
}
}
}
return res;
}
}

https://discuss.leetcode.com/topic/29303/two-end-bfs-in-java-31ms

Two-end BFS in Java 31ms.

Modified from Share my two-end BFS in C++ 80ms.

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
46
47
48
public class Solution {

public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
Set<String> beginSet = new HashSet<String>(), endSet = new HashSet<String>();

int len = 1;
int strLen = beginWord.length();
HashSet<String> visited = new HashSet<String>();

beginSet.add(beginWord);
endSet.add(endWord);
while (!beginSet.isEmpty() && !endSet.isEmpty()) {
if (beginSet.size() > endSet.size()) {
Set<String> set = beginSet;
beginSet = endSet;
endSet = set;
}

Set<String> temp = new HashSet<String>();
for (String word : beginSet) {
char[] chs = word.toCharArray();

for (int i = 0; i < chs.length; i++) {
for (char c = 'a'; c <= 'z'; c++) {
char old = chs[i];
chs[i] = c;
String target = String.valueOf(chs);

if (endSet.contains(target)) {
return len + 1;
}

if (!visited.contains(target) && wordList.contains(target)) {
temp.add(target);
visited.add(target);
}
chs[i] = old;
}
}
}

beginSet = temp;
len++;
}

return 0;
}
}

https://discuss.leetcode.com/topic/17890/another-accepted-java-solution-bfs

Another accepted Java solution (BFS)

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
46
public int ladderLength(String start, String end, Set<String> dict) {
// Use queue to help BFS
Queue<String> queue = new LinkedList<String>();
queue.add(start);
queue.add(null);

// Mark visited word
Set<String> visited = new HashSet<String>();
visited.add(start);

int level = 1;

while (!queue.isEmpty()) {
String str = queue.poll();

if (str != null) {
// Modify str's each character (so word distance is 1)
for (int i = 0; i < str.length(); i++) {
char[] chars = str.toCharArray();

for (char c = 'a'; c <= 'z'; c++) {
chars[i] = c;

String word = new String(chars);

// Found the end word
if (word.equals(end)) return level + 1;

// Put it to the queue
if (dict.contains(word) && !visited.contains(word)) {
queue.add(word);
visited.add(word);
}
}
}
} else {
level++;

if (!queue.isEmpty()) {
queue.add(null);
}
}
}

return 0;
}

谢谢你,可爱的朋友。