Leetcode/各大家 -- 127. Word Ladder(BFS)

127. Word Ladder（BFS）
Medium
https://leetcode.com/problems/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:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

For example,

Given:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]

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.

 Amazon LinkedIn Snapchat Facebook Yelp

思路： Use BFS to traverse dictionary. The level is composed of the words that are 1 char diff from curWord. If find such newWord, first check if is end word so we return min length, else check if in dict & remove it to avoid repeat.
4 loops in total: 1st queue.isEmpty(); 2nd queue.size() -- current level
                          3rd curword.length() - chose every char; 4th 'a' to 'z' - replace each char

 Note: if use DFS, we need to travel all path to decide the shortest one. If using BFS, we stop once we found since we start from short to find the path.解释

public class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) return 1;
        Set<String> set = new HashSet<>(wordList);
        Queue<String> q = new LinkedList<>();
        int len = 2;
        q.offer(beginWord);
        while(!q.isEmpty()){
            int size = q.size();
            for(int i = 0; i < size; i++){
                String cur = q.poll();
                for(int j = 0; j < cur.length(); j++){
                    StringBuilder sb = new StringBuilder(cur);
                    for(char c = 'a'; c <= 'z'; c++){
                        sb.setCharAt(j, c);
                        String tmp = sb.toString();
                        if(set.contains(tmp)){
                            if(tmp.equals(endWord)) return len;//endword need to be in dict
                            q.offer(tmp);
                            set.remove(tmp);
                        }
                    }
                }
            }
            len++;
        }
        return 0;
    }
}