[LeetCode] Word Ladder

Given two words (beginWord and endWord), and a dictionary's word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

Only one letter can be changed at a time
Each intermediate word must exist in the word list
For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.

Note:
Return 0 if there is no such transformation sequence.
All words have the same length.
All words contain only lowercase alphabetic characters.


Solution1 single-ended BFS
Typical shortest path problem, use BFS. When using BFS, need to mark visited string. In the problem, we can simply remove it from the dictionary set. Edge case check: remove beginWord from dictionary list if applicable. Tree grows from one side and become unevenly.
图片描述

Solution2 double-ended BFS
beginSet, endSet stores all the string reachable from beginWord, endWord respectively. The rest process is the same as single-ended BFS. Difference: in each iteration(of one level), use the set that has the fewer string. In this approach, tree grows evenly.
图片描述

public class Solution {
    public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
        if (beginWord.equals(endWord)) {
            return 1;
        }
        int len = 2;
        Queue<String> begin = new LinkedList<>();
        Queue<String> end = new LinkedList<>();
        begin.offer(beginWord);
        end.offer(endWord);
        if (wordList.contains(beginWord)) {
            wordList.remove(beginWord);
        }
        if (wordList.contains(endWord)) {
            wordList.remove(endWord);
        }
        
        
        while (!begin.isEmpty() && !end.isEmpty()) {
            if (begin.size() > end.size()) {
                Queue<String> temp = begin;
                begin = end;
                end = temp;
            }
            int size = begin.size();
            for (int i = 0; i < size; i++) {
                String word = begin.poll();
                char[] temp = word.toCharArray();
                for (int j = 0; j < temp.length; j++) {
                    char oldChar = temp[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        temp[j] = c;
                        String transformed = new String(temp);
                        if (end.contains(transformed)) {
                            return len;
                        } else if (wordList.contains(transformed)) {
                            wordList.remove(transformed);
                            begin.offer(transformed);
                        }
                    }
                    temp[j] = oldChar;
                }
            }
            len++;
        }
        return 0;
    }
}

评论

暂无评论