Super fast Java solution (two-end BFS)


  • 40

    Thanks to prime_tang and jianchao.li.fighter!

      public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        // hash set for both ends
        Set<String> set1 = new HashSet<String>();
        Set<String> set2 = new HashSet<String>();
        
        // initial words in both ends
        set1.add(start);
        set2.add(end);
        
        // we use a map to help construct the final result
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        
        // build the map
        helper(dict, set1, set2, map, false);
        
        List<List<String>> res = new ArrayList<List<String>>();
        List<String> sol = new ArrayList<String>(Arrays.asList(start));
        
        // recursively build the final result
        generateList(start, end, map, sol, res);
        
        return res;
      }
      
      boolean helper(Set<String> dict, Set<String> set1, Set<String> set2, Map<String, List<String>> map, boolean flip) {
        if (set1.isEmpty()) {
          return false;
        }
        
        if (set1.size() > set2.size()) {
          return helper(dict, set2, set1, map, !flip);
        }
        
        // remove words on current both ends from the dict
        dict.removeAll(set1);
        dict.removeAll(set2);
        
        // as we only need the shortest paths
        // we use a boolean value help early termination
        boolean done = false;
        
        // set for the next level
        Set<String> set = new HashSet<String>();
        
        // for each string in end 1
        for (String str : set1) {
          for (int i = 0; i < str.length(); i++) {
            char[] chars = str.toCharArray();
            
            // change one character for every position
            for (char ch = 'a'; ch <= 'z'; ch++) {
              chars[i] = ch;
              
              String word = new String(chars);
              
              // make sure we construct the tree in the correct direction
              String key = flip ? word : str;
              String val = flip ? str : word;
                  
              List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>();
                  
              if (set2.contains(word)) {
                done = true;
                
                list.add(val);
                map.put(key, list);
              } 
              
              if (!done && dict.contains(word)) {
                set.add(word);
                
                list.add(val);
                map.put(key, list);
              }
            }
          }
        }
        
        // early terminate if done is true
        return done || helper(dict, set2, set, map, !flip);
      }
      
      void generateList(String start, String end, Map<String, List<String>> map, List<String> sol, List<List<String>> res) {
        if (start.equals(end)) {
          res.add(new ArrayList<String>(sol));
          return;
        }
        
        // need this check in case the diff between start and end happens to be one
        // e.g "a", "c", {"a", "b", "c"}
        if (!map.containsKey(start)) {
          return;
        }
        
        for (String word : map.get(start)) {
          sol.add(word);
          generateList(word, end, map, sol, res);
          sol.remove(sol.size() - 1);
        }
      }

  • 0
    Q

    Good solution, thanks for sharing, I have two further improvements in return:

    1. There is no needs for helper method to return boolean. It is useless and can be more concise.
    2. List<String> list = map.containsKey(key) ? map.get(key) : new ArrayList<String>(); should be in the if block in order to save memory. Two if blocks can be merged into one block actually.

  • 0
    W

    Good job! But does anyone know how to analyze the time complexity? Thanks in advance!


  • 0
    N

    Why is flip variable used ?


  • 1
    8

    shouldn't we add a if(!list.contains(val)) to prevent adding the same string before each list.add(val)?


  • 0
    D

    Another point for optimization:

    No need for this

     if (!map.containsKey(start)) {
         return;
     }
    

    Simply put endWord to map. and in backtracking

    for (String word : map.get(start)) {
          sol.add(word);
          generateList(word, end, map, sol, res);
          sol.remove(sol.size() - 1);
    }
    

    test if map contains each word. if not, continue next loop.


  • 0

    @jeantimex Your method is amazing! The code is concise and clean.


  • 0

    @neer1304 Since you keep flip the begin set and end set, you have to make sure the graph you build is always from one direction to another.


  • 0
    A

    @YIIIIIIIIIIIIII Can you please provide a small example. Fail to understand this flip concept. Thanks in advance.


Log in to reply
 

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