Leetcode127. 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 transformed word must exist in the word list.
Note:

<!-- more -->

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.
Example 1:

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

Output: 5

Explanation: As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
return its length 5.
Example 2:

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

Output: 0

Explanation: The endWord "cog" is not in wordList, therefore no possible transformation.

思路

两种方法：
BFS使用队列；使用双向BFS，使用HashSet
双向BFS:
将wordlist放入HashSet中，如果最后的endword不在wordlist中，直接返回0。将startword和endword放入HashSet中，设step为0，当start 和end不为空时进入循环，当进入到循环后，step++，为保证平衡，当start的size大于end的size，交换end和star。设定一个临时的hashset。根据start里的word，每个位置替换26个字母，如果新的word在endword当中存在，返回step+1.如果wordlist没有新的word，继续循环。否则代表还没到end且wordlist中含有新的word，则将wordlist中的该元素去除（如若重复使用，长度必将增大），result中加入新的word。最后将word改回原来的值并将暂时的result作为start开启下一轮循环。

代码

//BFS使用队列
//使用双向BFS，使用HashSet
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordlist= new HashSet<>();
        for(String word: wordList){
            wordlist.add(word);
        }
        if(!wordlist.contains(endWord))
            return 0;
        HashSet<String> start = new HashSet<>(); 
        HashSet<String> end = new HashSet<>(); 
        int step=0;
        start.add(beginWord);
        end.add(endWord);
        while(!start.isEmpty()&&!end.isEmpty()){
            ++step;
            if(start.size()>end.size()){//当start的大小比end大时，交换两个set以保证平衡
                HashSet<String> cur = new HashSet<>(); 
                cur = end;
                end = start;
                start = cur;
            }
            HashSet<String> result = new HashSet<>(); 
            for(String word: start){
                char[] ch = word.toCharArray();
                for(int i=0;i<beginWord.length();i++){
                    char c = ch[i];
                    for(char j='a';j<='z';j++){
                        ch[i]=j;
                        String w = new String(ch);
                        if(end.contains(w)) return step+1;
                        if(!wordlist.contains(w)) continue;
                        wordlist.remove(w);
                        result.add(w);
                    }
                    ch[i]=c;
                }
            }
            start = result;
        }
        return 0;  
    }
}