My accepted Java solution using BFS and DFS


  • 0
    E

    The basic idea is to backtrack from the endWord to the startWord.
    I used bfs to find out the distance of each word to the startWord, and the words that are connected to it (one char different).
    Then I used dfs to find each path.

    public static List<List<String>> findLadders(String startWord, String endWord, List<String> wordList) {
          List<List<String>> ladders = new ArrayList<>();
          if(wordList.contains(endWord)){
             return ladders;
          }
          //map the word with connected words.
          Map<String, List<String>> map = new HashMap<>();
          //map the word with its distance to the start.
          Map<String, Integer> distance = new HashMap<>();
          
          wordList.add(startWord);
          
          //Fill in map, and distance.
          bfs(map, distance, startWord, endWord, wordList);
          
          List<String> path = new ArrayList<>();
          //add endWord to path since we are backtracing.
          path.add(endWord);
          
          //find each path. 
          dfs(ladders, path, startWord, endWord, distance, map);
          return ladders;
       }
       
       
       public static void dfs(List<List<String>> ladders, List<String> path, String start, String crt, Map<String, Integer> distance, Map<String,List<String>> map){
          if(crt.equals(start)){
             Collections.reverse(path);
             ladders.add(new ArrayList<String> (path));
             Collections.reverse(path);
             return;
          }  
          
          for(String next: map.get(crt)){
             //makes sure that crt is closer to the start.
             if(distance.get(crt) == distance.get(next)+1){
                path.add(next);
                dfs(ladders, path, start, next, distance, map);
                path.remove(path.size() - 1);
             }
          }
          
          
       }
       public static void bfs(Map<String, List<String>> map, Map<String, Integer> distance, String start, String end, List<String> wordList) {
          Queue<String> q = new LinkedList<>();
          q.offer(start);
          distance.put(start, 0);
          for(String s: wordList) {
             map.put(s, new ArrayList<String>());
          }
          while(!q.isEmpty()){
             String crt = q.poll();
             List<String> nextWords = getNextWord(crt, wordList);
             for(String next: nextWords){
                map.get(next).add(crt);
                if(!distance.containsKey(next)){
                   distance.put(next, distance.get(crt)+1);
                   q.offer(next);
                }
             }
          }
       }
       
       //return a list of strings that are connected with the word.
       public static List<String> getNextWord (String word, List<String> wordList){
          List<String> result = new ArrayList<>();
          for(String nextWord: wordList){
             if(!word.equals(nextWord) && isConnected(word, nextWord)){
                result.add(nextWord);
             }
          }
          return result; 
       }
    
       //check if two words are connected.
       public static boolean isConnected (String word, String nextWord){
          boolean connected = true;
          int changedIndex = 0;
          for(int i = 0; i < word.length(); i++){
             if(word.charAt(i) != nextWord.charAt(i)){
                changedIndex ++;
                if(changedIndex > 1){
                   connected = false;
                   break;
                }
             }
          }
          return connected;
       }
    
    

    The run time for my getNextWord is O(N*L) (N words, each with length L), it can be O(L^2) with the following function:

    public static List<String> getNextWord (String word, List<String> wordList){
          List<String> result = new ArrayList<>();
          for(int index = 0; index < word.length(); index++){
             for(char c = 'a';  c < 'z'; c++){
                String newWord = word.substring(0, index) + c + word.substring(index + 1, word.length());
                if(wordList.contains(newWord)){
                   result.add(newWord);
                }
             }
          }
          return result;
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.