Super fast Java solution using two-end BFS


  • 19

    Thanks to prime_tang!

    public class Solution {
        public int ladderLength(String start, String end, Set<String> dict) {
            Set<String> set1 = new HashSet<String>();
            Set<String> set2 = new HashSet<String>();
            
            set1.add(start);
            set2.add(end);
            
            return helper(dict, set1, set2, 1);
        }
        
        int helper(Set<String> dict, Set<String> set1, Set<String> set2, int level) {
            if (set1.isEmpty()) return 0;
            
            if (set1.size() > set2.size()) return helper(dict, set2, set1, level);
            
            // remove words from both ends
            for (String word : set1) { dict.remove(word); };
            for (String word : set2) { dict.remove(word); };
            
            // the set for next level
            Set<String> set = new HashSet<String>();
            
            // for each string in the current level
            for (String str : set1) {
                for (int i = 0; i < str.length(); i++) {
                    char[] chars = str.toCharArray();
                    
                    // change letter at every position
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String word = new String(chars);
                        
                        // found the word in other end(set)
                        if (set2.contains(word)) {
                            return level + 1;
                        }
                        
                        // if not, add to the next level
                        if (dict.contains(word)) {
                            set.add(word);
                        }
                    }
                }
            }
            
            return helper(dict, set2, set, level + 1);
        }
    }

  • 5
    Q

    Elegant solution! Thank you for sharing. Two further improvements.

    1. for (String word : set1) { dict.remove(word); }; can be replace by dict.removeAll(set1)
    2. char[] chars = str.toCharArray(); put it outside of second for loop can be faster(also need to record the original char and recover), since Java uses System.arraycopy to implement str.toCharArray() method. This can be N times faster. N is the length of word.

  • 0
    M

    nice improvements!


  • 0
    C

    it is not good to remove word in dict


  • -1
    J
    This post is deleted!

  • 0
    J

    Sorry, seems like the No2 is wrong.


  • 0
    Q

    Pls read it more carefully.


  • 0
    M

    beautiful! We could just remove the word from dict as soon as we find a hit right?! It works fine for test cases here. Not entirely sure if it's theoretically correct.


  • 1
    S

    Seems like we need to check if the endWord exists in the dictionary before we call the helper, or it won't pass the test case where the endWord does not exist in the dictionary but some words with 1 distance to the endWord exists in the dictionary.
    For example,

    Input :
    "hit"
    "cog"
    ["hot","dot","dog","lot","log"]
    Output: 5
    Expected: 0

    Fix this problem to add

      if(!dict.contains(end)) {
                return 0;
            }
    

    before call helper.


Log in to reply
 

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