Share my Java solution


  • 0
    D

    Basic idea:

    1. BFS in the dict graph, each time we change one character of current word to become a new word

    2. We store the prev word of current word into a HashMap, so we can backtracing the path from end word to start word

    3. Trim unnecessary branches
      3.1. we use a HashMap to store the level of a word in the dict graph. We only add new word to queue if we never hit this word. We skip the prev info computation of a new word once we have processed this word in upper level.
      3.2 remove the popped word from dict because we should not hit it again, all the following occurrence are in the next level.

      public List<List<String>> findLadders(String start, String end, Set<String> dict) {

       LinkedList<String> queue = new LinkedList<>();
       String lastWordInLevel = start;
       
       queue.add(start);
       int level = 0;
       int minLevel = Integer.MAX_VALUE;
       
       dict.add(end);
       dict.remove(start);
       
       Map<String, List<String>> preMap = new HashMap<>();     // store the previous word of the key word in the result chain
       Map<String, Integer> wordLevel = new HashMap<>();       // store the level of word
       
       while (!queue.isEmpty()) {
           
           String word = queue.poll();
           dict.remove(word);             // every time remove the popped word because we should not come back again
           
           if (word.equals(end)) {
           	break;
           }
           
           for (int i = 0; i < word.length(); i++) {
               StringBuilder nextWordBuf = new StringBuilder(word);
               for (char c = 'a'; c <= 'z'; c++) {
                   if (c != word.charAt(i)) {
                       nextWordBuf.setCharAt(i, c);
                       String nextWord = nextWordBuf.toString();
                       if (dict.contains(nextWord)) {
                           if (!wordLevel.containsKey(nextWord)) { // A unprocessed next word
                           	wordLevel.put(nextWord, level+1); // update its level
                           	queue.add(nextWord);    // push the unprocessed word to queue
                           }
                           // we met this nextWord in upper level before, skip this one
                           if (wordLevel.get(nextWord) < (level+1)){
                       		continue;
                       	}
      
                           // add current word to the prevList of nextWord
                           List<String> preList = preMap.containsKey(nextWord)?preMap.get(nextWord):(new ArrayList<String>());
                           preList.add(word);
                           preMap.put(nextWord, preList);
                       }
                   }
               }
           }
           
           if (word.equals(lastWordInLevel)) { // process level info
               lastWordInLevel = queue.peekLast();
               level ++;
           }
       }
       
       List<List<String>> rets = new ArrayList<>();
       LinkedList<String> curRet = new LinkedList<>();
       curRet.add(end);
       buildPath(preMap, start, end, curRet, rets);
       return rets;
      

      }

      private void buildPath(Map<String, List<String>> preMap, String start, String end, LinkedList<String> curRet, List<List<String>> rets) {
      if (end.equals(start)) {
      List<String> newRet = new ArrayList<>(curRet);
      rets.add(newRet);
      return;
      }
      List<String> list = preMap.get(end);
      if (list == null) return;
      for (String preWord : list) {
      curRet.addFirst(preWord);
      buildPath(preMap, start, preWord, curRet, rets);
      curRet.removeFirst();
      }
      }


Log in to reply
 

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