My 104ms Simple Java Solution


  • 1
    J

    Hi all,

    I wrote a very short and relatively fast Java solution:

    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
            Queue<String> queue = new ArrayDeque<>();
            Queue<Integer> distQueue = new ArrayDeque<>();
            queue.offer(beginWord);
            distQueue.offer(1);
            wordList.remove(beginWord);
            wordList.add(endWord);
            while (!queue.isEmpty()) {
                String cur = queue.poll();
                int len = distQueue.poll();
                if (endWord.equals(cur)) return len;
                char[] chars = cur.toCharArray();
                for (int i = 0; i < chars.length; i++) {
                    for (char j = 'a'; j <='z'; j++) {
                        if (chars[i] == j) continue;
                        char temp = chars[i];
                        chars[i] = j;
                        String next = new String(chars);
                        if (wordList.contains(next)) {
                            queue.offer(next);
                            distQueue.offer(len + 1);
                            wordList.remove(next);
                        }
                        chars[i] = temp;
                    }
                }
            }
            return 0;
        }
    

    Note the distQueue is used to keep track of the distance of items in queue.


  • 0
    J

    Very short and nice code! Thanks for sharing.


Log in to reply
 

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