A 25-line 1204ms BFS solution


  • 1
    H

    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];
            }
        };

  • 4
    R

    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];
            }
    };

  • 0
    N

    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?


  • 0
    L

    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;
    }
    

    };


  • 0
    I

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


  • 0
    I

    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;
        }
    };
    

  • 0
    R

    Then it is your problem.


  • 0
    I

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


  • 1
    M

    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<>();
            queue.add(start);
            queue.add(null);
            visited.add(start);
            int len = 1;
            while (true) {
                String str = queue.remove();
                if (str == null) {
                    if (queue.isEmpty()) {
                        return 0;
                    }
                    queue.add(null);
                    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)) {
                            queue.add(newStr);
                            visited.add(newStr);
                        }
                    }
                }
            }
        }
    }

  • 0
    A
    This post is deleted!

  • 0
    T

    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.


  • 0
    H

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


  • 2
    H

    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);
            q.add(beginWord);
            
            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);
                            q.add(temp);
                        }
                    }
                }
            }
            if (dis.get(endWord) == null) return 0;
            return dis.get(endWord);
        }
    }

Log in to reply
 

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