Beat 99.01% java solution


  • 1
    F
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            return ladderLength(Collections.singleton(beginWord), Collections.singleton(endWord), wordList, 2);
        }
    
        private int ladderLength(Set<String> beginWords, Set<String> endWords, Set<String> wordList, int len) {
            if (beginWords.size() == 0) {
                return 0;
            }
            Set<String> middleWords = new HashSet<>();
            for (String beginWord : beginWords) {
                char[] chars = beginWord.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    char aChar = chars[i];
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        chars[i] = ch;
                        String s = String.valueOf(chars);
                        if (endWords.contains(s)) {
                            return len;
                        } else if (wordList.contains(s)) {
                            middleWords.add(s);
                            wordList.remove(s);
                        }
                    }
                    chars[i] = aChar;
                }
            }
            if (middleWords.size() < endWords.size()) {
                return ladderLength(middleWords, endWords, wordList, len + 1);
            } else {
                return ladderLength(endWords, middleWords, wordList, len + 1);
            }
        }

  • 0
    G

    can u please explain your idea ? I don't get why you need Set<String> for beginWords & endWords, and what is middleWords ? and not sure why "int len" is starts from 2 either.


  • 0
    L

    Hope the following explanation can help you. Of course, since I am not the original author of this solution, it may mislead you.

    1. Middle word is the words during the transition. For instance, "hot" -> "dot" -> "dog" are the middle words in the example given by the problem.
    2. BeginWords and endWords are changed during the recursion. It could be the middleWords or endWords due to:
    if (middleWords.size() < endWords.size()) {
        return ladderLength(middleWords, endWords, wordList, len + 1);
    } else {
         return ladderLength(endWords, middleWords, wordList, len + 1);
    }
    
    1. Why? The author may want to save time by starting the look up from a smaller word set. But the steps of the transition keep increasing no matter what the direction of the search is, forwards or backwards.
    2. The recursion stops at when the forward lookup and backward lookup get connected. That means the situation when the word in the beginning word set only has 1 bit difference with the word in the endSet.
    if (endWords.contains(s)) {
                            return len;
    
    1. Actually you will see if there is a solution in the input, the minimum len is 2. If no solution is found, then it is zero. So the len starts from 2.

  • 0
    T

    Awesome solution.


  • 0
    M

    Can someone explain why this "recursive version" is much faster than my "while loop version"?

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            Queue<String> nodes = new LinkedList<String>();
            wordList.add(endWord);
            wordList.remove(beginWord);
            
            nodes.offer(beginWord);
            int length = 1;
            int size;
            while(nodes.size() > 0) {
                size = nodes.size();
                
                for(int i = 0; i < size; i++) {
                    String tmp = nodes.poll();
                    
                    for(int j = 0; j < tmp.length(); j++) { 
                        for(int al = 0; al < 26; al++) {
                            char c = (char)('a' + al);
                            String neighbours = tmp.substring(0, j) + c + tmp.substring(j + 1, tmp.length());
                            if(neighbours.equals(endWord)) 
                                return length + 1;
                            if(wordList.contains(neighbours)) {
                                nodes.offer(neighbours);
                                wordList.remove(neighbours);
                            }
                        }
                    }
                }
                length++;
            }
            
            return 0;
        }
    

  • 0

    @Mirando

    I am not sure.

    All I know is sometimes it really depends on how they set test cases. Your BFS is good as well.


Log in to reply
 

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