# A 25-line 1204ms BFS solution

• As suggested by the title, the following is a BFS solution. Any suggestion for improvement of my code is welcome. Is there any other solution better than BFS?

``````class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_map<string, int> dis; // store the distance from start to the current word
queue<string> q; // FIFO for bfs purpose
dis[start] = 1;
q.push(start);
while (!q.empty()) {
string word = q.front(); q.pop();
if (word == end) break;
for (int i = 0; i < word.size(); i++) {
for (int j = 0; j < 26; j++) {
string newWord = word;
newWord[i] = 'a' + j;
if ((dict.count(newWord) > 0 || newWord == end) && dis.count(newWord) == 0) {
dis[newWord] = dis[word] + 1;
q.push(newWord);
}
}
}
}
if (dis.count(end) == 0) return 0;
return dis[end];
}
};``````

• I think this is a nice method. Here are some improvements. By making them the time required is down to 716ms.
I guess it is not needed to write comments since it is based on your solution.

``````class Solution {
public:
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
unordered_map<string, int> dis; // store the distance from start to the current word
queue<string> q; // FIFO for bfs purpose
dis[start] = 1;
q.push(start);
while (!q.empty()) {
string word = q.front(); q.pop();
if (word == end) break;
for (int i = 0; i < word.size(); i++) {
string temp = word;
for (char c = 'a'; c <= 'z'; c++) {
temp[i] =c;
if (dict.count(temp) > 0 && dis.count(temp) == 0) {
dis[temp] = dis[word] + 1;
q.push(temp);
}
}
}
}
if (dis.count(end) == 0) return 0;
return dis[end];
}
};``````

• Your code seems can not pass the example case, beacuse your code does not handle the end string well."if (word == end) break;", however, if end string is not in dict, it can not be pushed into the queue. Right?

• I have a solution without storing the distance in a collection:

class Solution {

public:
int ladderLength(string start, string end, unordered_set<string> &dict) {

``````	dict.erase(start);
dict.erase(end);
int currentLength = 2;
int currentBatchCount = 1;
int nextBatchCount = 0;

queue<string> q;

q.push(start);

while (!q.empty()){

string current = q.front();
q.pop();

for (int i = 0; i < current.size(); i++){
string var = current;
for (int c = 'a'; c <= 'z'; c++){
var[i] = c;
if (var == end){
return currentLength;
}

if (dict.count(var) > 0){
q.push(var);
dict.erase(var);
nextBatchCount++;
}
}
}

currentBatchCount--;

if (currentBatchCount == 0){
currentLength++;
currentBatchCount = nextBatchCount;
nextBatchCount = 0;
}
}

return 0;
}
``````

};

• both solutions provided by the op and this one cannot even correctly solve the example hit->cog transformation. Wonder why it's ACed.

• This is a modified version based on OP's code. Handles end correctly, per the reply of nianglao.

class Solution {
public:
int ladderLength(string start, string end, unordered_set<string> &dict) {
// edge case
if (start == end)
return 1;

``````        unordered_map<string, int> usi; // usi for the transformation distance
queue<string> qs;
qs.push(start);
usi[start] = 1;
while(!qs.empty()) {
string cur = qs.front(); qs.pop();
for (int i{0}; i < cur.size(); ++i) {
string tmp{cur};
for (char ch{'a'}; ch <= 'z'; ++ch) {
tmp[i] = ch;
if (tmp == end) {
return usi[cur]+1;
}
if (dict.count(tmp) > 0 && usi.count(tmp) == 0) {
qs.push(tmp);
usi[tmp] = usi[cur]+1;
}
}
}
}
return 0;
}
};
``````

• Then it is your problem.

• It's rhetorical. And I bet you know what's wrong as it's manifest.

• Here's a Java version of BFS solution.

``````public class Solution {
public int ladderLength(String start, String end, Set<String> dict) {
if (start == null || end == null) return 0;
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
int len = 1;
while (true) {
String str = queue.remove();
if (str == null) {
if (queue.isEmpty()) {
return 0;
}
len++;
continue;
} else if (str.equals(end)) {
return len;
}
for (int i = 0; i < str.length(); i++) {
char[] charArray = str.toCharArray();
for (char c = 'a'; c <= 'z'; c++) { // optional if (c != charArray[i]) condition check here
charArray[i] = c;
String newStr = new String(charArray);
if (dict.contains(newStr) && !visited.contains(newStr)) {
}
}
}
}
}
}``````

• This post is deleted!

• you guys used set::count to determine if a element is contained in the set, but I think set::find is a little faster that avoids of traversing all the elements in the set.

• Yes, you are right. I have now updated my solution to fix that bug. Thanks.

• Here is my version of Java code:

``````public class Solution {
public int ladderLength(String beginWord, String endWord, Set<String> wordDict) {
Map<String, Integer> dis = new HashMap<String, Integer>();
Queue<String> q = new LinkedList<String>();
dis.put(beginWord, 1);

while (!q.isEmpty()) {
String word = q.remove();
int len = dis.get(word);
if (word.equals(endWord)) break;
for (int i = 0; i < word.length(); i++) {
String temp = word;
for (char ch = 'a'; ch <= 'z'; ch++) {
// replace a specific character in a string
char[] arr = temp.toCharArray();
arr[i] = ch;
temp = new String(arr);
if (!dis.containsKey(temp) && wordDict.contains(temp)) {
dis.put(temp, len + 1);
}
}
}
}
if (dis.get(endWord) == null) return 0;
return dis.get(endWord);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.