127. Word Ladder

Link

Solution

one way BFS: 將startWord把每個位置的字母替換成a-z看看是否存在於wordlist中 如果存在就把他們放回queue中，並再重新根據他們重複替換a-z等上述步驟，直到能夠變成endWord

T: O(n*26*l) , n : wordlist length, l : word length, just consider all possibilities of changing a-z of word in wordlist

理論上會檢查所有wordlist中的word，並檢視word中每個字母變換成a-z帶來的結果

S: O(n)

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<String>(wordList);
        Queue<String> toTest = new LinkedList<>();
        
        //Set<String> toTestSet = new HashSet<>();
        toTest.add(beginWord);
        int count = 1;
        while(!toTest.isEmpty()){
            int size = toTest.size();
            for(int k = 0; k < size; k++){
                String s = toTest.poll();
                for(int i = 0; i < s.length(); i++){
                    char c = s.charAt(i);
                    if(s.equals(endWord)) return count;
                    for(int j = 0; j < 26; j++){
                        s = s.substring(0,i) + (char)('a' + j )+ s.substring(i+1);
                        if(words.contains(s)){
                            words.remove(s);
                            toTest.add(s);
                        }
                    }
                    s = s.substring(0,i) + c + s.substring(i+1);
                }
            }
            count++; 
        }
        return 0;
    }

Bi-direction BFS

T: O((n*26*l )/ 2) , n : wordlist length, l : word length, search time reduce to 1/2, since it meets in the middle. S: O(n)

  public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> words = new HashSet<String>(wordList);
        if(!words.contains(endWord)) return 0;
        Set<String> s1 = new HashSet<>();
        Set<String> s2 = new HashSet<>();
        
        s1.add(beginWord);
        s2.add(endWord);
        int count = 1;
        //will update the s1 by next candidates
        while(!s1.isEmpty() && !s2.isEmpty()){
            
            //Swap s1,s2 make sure we are checking the smaller set
            if(s1.size() > s2.size()){
                Set<String> temp = s1;
                s1 = s2;
                s2 = temp;
            }
            
            Set<String> candidates = new HashSet<>();
            //for generating the candidates, and also check if s2 has the elements already
            for(String s : s1){
                for(int i = 0; i < s.length(); i++){
                    char c = s.charAt(i);
                    for(int j = 0; j < 26; j++){
                        s = s.substring(0,i) + (char)('a' + j )+ s.substring(i+1);
                        if(s2.contains(s)) return count+1;

                        if(words.contains(s)){
                            words.remove(s);
                            candidates.add(s);
                        }
                    }
                    s = s.substring(0,i) + c + s.substring(i+1);
                }
            }
            s1 = candidates;
            count++; 
        }
        return 0;
    }