127. Word Ladder

题目描述

Given two words (beginWordandendWord), and a dictionary's word list, find the length of shortest transformation sequence frombeginWordtoendWord, 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 length5.

解题方法

BFS:

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)){
            return 1;
        }
        Set<String> dic = new HashSet<String>();
        for(String word : wordList){
            dic.add(word);
        }

        Set<String> hash = new HashSet<String>();
        Queue<String> queue = new LinkedList<String>();
        hash.add(beginWord);
        queue.offer(beginWord);
        int count = 1;
        while(!queue.isEmpty()){
            int size = queue.size();
            count++;
            for(int i = 0; i < size; i++){
                String word = queue.poll();
                //System.out.println(word);
                for(String nextword : getNextWords(word, dic)){
                    if(hash.contains(nextword)){
                        continue;
                    }

                    if(nextword.equals(endWord)){
                        return count;
                    }

                    hash.add(nextword);
                    queue.offer(nextword);
                }
            }
        }
        return 0;
    }

    private String replace(String s, int index, char c){
        char[] chars = s.toCharArray();
        chars[index] = c;
        return new String(chars);
    }

    private ArrayList<String> getNextWords(String word, Set<String> dic){
        ArrayList<String> nextWords = new ArrayList<String>();
        for(char c = 'a'; c <= 'z'; c++){
            for(int i = 0; i< word.length(); i++){
                if(word.charAt(i) == c){
                    continue;
                }
                String nextword = replace(word, i, c); 
                //String nextword = word.substring(0, i) + c + word.substring(i + 1);
                if(dic.contains(nextword)){
                    nextWords.add(nextword);
                }
            }
        }
        return nextWords;
    }*/








    //Using space to save time
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        //Coner case
        if(beginWord.equals(endWord)){
            return 1;
        }

        Set<String> visited = new HashSet<>();
        visited.add(beginWord);
        visited.add(endWord);

        Set<String> dic = new HashSet<>();
        for(String word: wordList){
            dic.add(word);
        }
        if(!dic.contains(endWord)){
            return 0;
        }

        Set<String> begin = new HashSet<>();
        Set<String> end = new HashSet<>();
        int step = 0;
        begin.add(beginWord);
        end.add(endWord);
        while(!begin.isEmpty() && !end.isEmpty()){
            step++;
            Set<String> nextLevel = new HashSet<>();

            // swap begin and end sets  : 掃短的
            if(begin.size() > end.size()){ 
                Set<String> temp = begin;
                begin = end;
                end = temp;
            }

            //Polling the begin set
            for(String word: begin){
                //Get wordSets
                Set<String> nxtWords = replace(word, dic);
                for(String nxtWord : nxtWords){
                    if(end.contains(nxtWord)){
                        return step + 1;
                    }

                    if(dic.contains(nxtWord) && visited.add(nxtWord)){
                        nextLevel.add(nxtWord);  //中間產生出新的一層
                    }
                }
            }
            begin = nextLevel;
        }

        return 0;
    }

    private Set<String> replace(String word, Set<String> dic){
        Set<String> words = new HashSet<>();
        for(int i = 0; i < word.length(); i++){
            for(char ch = 'a'; ch <= 'z'; ch++){
                if(word.charAt(i) == ch){
                    continue;
                }
                String newWord = word.substring(0, i) + ch + word.substring(i + 1);
                if(dic.contains(newWord)){
                    words.add(newWord);
                }
            }
        }
        return words;
    }