127. Word Ladder

Problem:

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.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

5/19/2018 update:
不用map也可以做，map没啥用，故弄玄虚。分层BFS用queue.size()控制就行了。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if (wordList == null || wordList.size() == 0)
            return 0;
        int res = 1;
        Set<String> set = new HashSet<>(wordList);
        if (set.contains(beginWord)) {
            set.remove(beginWord);
        }
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        while (!queue.isEmpty()) {
            int size = queue.size();
            res++;
            for (int j = 0; j < size; j++) {
                String cur = queue.poll();
                for (int i = 0; i < cur.length(); i++) {
                    char[] temp = cur.toCharArray();
                    for (char c = 'a'; c <= 'z'; c++) {
                        temp[i] = c;
                        String tempStr = new String(temp);
                        if (set.contains(tempStr)) {
                            if (tempStr.equals(endWord)) return res;

                            queue.offer(tempStr);
                            set.remove(tempStr);

                        }
                    }
                }
            }

        }
        return 0;
    }
}

Analysis:

Search from the beginWord, find the next words from wordList. Use set to memorize visited words, use map to store distance from current word to beginWord. 

Solution: 

写得越来越准了，几乎是one pass。才开始刷题的时候每道题起码要改5,6遍语法错误。

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> set = new HashSet<>(wordList);
        Map<String, Integer> map = new HashMap<>();
        if (set.contains(beginWord)) {
            set.remove(beginWord);
        }

        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        map.put(beginWord, 1);
        while(!queue.isEmpty()) {
            String curWord = queue.poll();
            int level = map.get(curWord);
            for (int i = 0; i < curWord.length(); i++) {
                char[] temp = curWord.toCharArray();
                for (char j = 'a'; j <= 'z'; j++) {
                    temp[i] = j;
                    String newWord = new String(temp);
                    if (set.contains(newWord)) {
                        if (endWord.equals(newWord)) return level + 1;
                        set.remove(newWord);
                        queue.offer(newWord);
                        map.put(newWord, level + 1);
                    }
                }
            }
        }

        return 0;
    }
}