Word Ladder

Linkage

https://leetcode.com/problems/word-ladder/description/

Naive Code

In the naive implementation, we will consider all words as the node in graph, then using BFS to record the shortest depth. Once we visit endWord, then we return the current depth.

import java.util.Queue;

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        int[] depth_array = new int[ wordList.size() ]; //The last in depth_array is beginWord
        for (int i = 0; i < wordList.size(); i++) {
            depth_array[i] = 0;
        }
        List<String> targetWordList = findNext(beginWord, wordList, depth_array, 0);
        for (String nextWord : targetWordList) {
            if ( nextWord.equals(endWord) ) {
                return 2;
            }else {
                queue.offer(nextWord);
            }
        }
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            int currentDepth = depth_array[ wordList.indexOf(currentWord) ];
            System.out.println(currentDepth);
            targetWordList = findNext(currentWord, wordList, depth_array, currentDepth);
            for (String nextWord : targetWordList) {
                if ( nextWord.equals(endWord) ) {
                    return currentDepth + 2;
                }else {
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
        
    }
    
    public boolean isNext(String beginWord, String endWord) {
        int countOfDifferentChar = 0;
        for(int i = 0; i < beginWord.length(); i++) {
            if( beginWord.charAt(i) != endWord.charAt(i) ) {
                countOfDifferentChar += 1;
            }
        }
        return countOfDifferentChar == 1 ? true : false;
    }
    
    public List<String> findNext(String beginWord, List<String> wordList, int [] depth_array, int depth) {
        List<String> retWordList = new ArrayList<String>();
        for (int i = 0; i < wordList.size(); i++){
            if ( depth_array[i] == 0 && isNext(beginWord, wordList.get(i) ) == true ) {
                retWordList.add( wordList.get(i) );
                depth_array[i] = depth + 1;
            }
        }
        return retWordList;
    }
    

}

Improve Code

In the naive implementation. each time to find the next word on the chain ,we need to traverse all the node in the all graph, which is time-consuming(The test cases improve this). The wiser way is to dectect new node by substitute each letter in the current word,(The consumed time is word_length*26)

import java.util.Queue;
import java.util.HashMap;
class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        Queue<String> queue = new LinkedList<String>();
        HashMap<String, Integer> map = new HashMap();
        
        for (String word : wordList) {
            map.put(word, 0);
        }
        
        List<String> targetWordList = findNext(beginWord, wordList, map, 0);
        for (String nextWord : targetWordList) {
            if ( nextWord.equals(endWord) ) {
                return 2;
            }else {
                queue.offer(nextWord);
            }
        }
        
        while(queue.isEmpty() == false) {
            String currentWord = queue.poll();
            int currentDepth = map.get(currentWord);
            targetWordList = findNext(currentWord, wordList, map, currentDepth);
            for (String nextWord : targetWordList) {
                if ( nextWord.equals(endWord) ) {
                    return currentDepth + 2;
                }else {
                    queue.offer(nextWord);
                }
            }
        }
        return 0;
        
    }
    
    public List<String> findNext(String beginWord, List<String> wordList, HashMap<String, Integer> map, int depth) {
        List<String> retWordList = new ArrayList<String>();
        for(int position = 0; position < beginWord.length(); position += 1) {
            for (int index = 0; index < 26; index++){
                char replace = (char) ('a' + index);
                String newWord = beginWord.substring(0, position) + replace + beginWord.substring(position+1, beginWord.length()); 
                Integer word_distance = map.get(newWord);
                if (word_distance != null && word_distance == 0) {
                    retWordList.add(newWord);
                    map.put(newWord,  depth + 1);
                }
            }
        }
        
        return retWordList;
    }
    

}