New Java AC solution (Revised from previous set version)


  • 4

    Previous word ladder problem uses Set as wordList, and in previous test cases, the endWord seems always in the wordList (correct me if I am wrong). I still use the same idea as described here: https://discuss.leetcode.com/topic/17890/another-accepted-java-solution-bfs/8
    Modified a bit since we need to check if the transformed word is in wordList or not.

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            Set<String> words = new HashSet<>();
            words.addAll(wordList);
            
            Queue<String> queue = new LinkedList<>();
            queue.add(beginWord);
    
            Set<String> reached = new HashSet<>();
            reached.add(beginWord);
            
            int level = 1;
            while (!queue.isEmpty()) {
                int size = queue.size();
                
                for (int i = 0; i < size; i++) {
                    String word = queue.poll();
                    for (int j = 0; j < word.length(); j++) {
                        char[] chars = word.toCharArray();
                        
                        for (char c = 'a'; c <= 'z'; c++) {
                            chars[j] = c;
                            String newWord = new String(chars);
                            if (words.contains(newWord)) {
                                if (newWord.equals(endWord)) return level + 1;
                                else if (reached.add(newWord)) queue.add(newWord);
                            }
                        }
                    }
                }
                level++;
            }
            return 0;
        }
    

  • 0
    E

    @cammyluffy
    Great!


Log in to reply
 

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