L127 Word Ladder

BFS

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.

problem analysis:

• what we want is to find the word's transform process. For this question, we only need to find the total of the step.

Solution:

BFS / (bidirectional BFS)

TC: O(n*l) where n is the number of words in word list and l is the the length of each word

SC: O(n)

• If the word has already used, this word will not be used again, since the word will be repeated again and again

• imagine each level has the all combination with a letter.

public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> dict = new HashSet<>();
        for(String word: wordList) dict.add(word);
        if(!dict.contains(endWord)) return 0;
        
        Queue<String> q = new ArrayDeque<>();
        q.offer(beginWord);
        
        int l = beginWord.length();
        int steps = 0;
        
        while(!q.isEmpty()){
            steps++;
            for(int s = q.size(); s > 0; s--){
                String w = q.poll();
                char[] chars = w.toCharArray();
                for(int i = 0; i < l; i++){
                    char ch = chars[i];
                    for(char c ='a'; c <='z'; c++){
                        if(c == ch) continue;
                        chars[i] = c;
                        String t = new String(chars);
                        if(t.equals(endWord)) return steps+1;
                        if(!dict.contains(t)) continue;
                        dict.remove(t);
                        q.offer(t);
                    }
                    chars[i] = ch;
                }
            }
        }
        return 0;
    }