[Java] accepted code.. not ideal performance.. what do I need to improve?


  • 0
    B

    Algorithm: BFS

    Ideas:

    1. records the minimum cost to reach any node

    2. records the parents of each node

    3. avoids revisiting node (with higher cost) by comparing the current cost against the minimum cost

    4. retrace and generate the result by using the parents map


    In the code: 3 things outside the loop:

    1. parents -> parents of each node

    2. depths -> the minimum cost to reach any node from start

    3. nextToEnd -> the nodes next to the end

    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    
        Queue<String> nodeQueue = new LinkedList<>();
        nodeQueue.add(start);
        nodeQueue.add(null);
        int depth = 1;
    
        Map<String, Set<String>> parents = new HashMap<>();
        Map<String, Integer> depths = new HashMap<>();
        Set<String> nextToEnds = new HashSet<>();
    
        while(!nodeQueue.isEmpty()) {
          String node = nodeQueue.remove();
          if(node == null) {
            if(nodeQueue.isEmpty())
              break;
            if(!nextToEnds.isEmpty())
              break;
            depth++;
            nodeQueue.add(null);
            continue;
          }
          for(int i = 0; i < node.length(); i++) {
            StringBuilder builder = new StringBuilder(node);
            for(char j = 'a'; j <= 'z'; j++) {
              builder.setCharAt(i, j);
              String mutation = builder.toString();
              if(mutation.equals(node))
                continue;
    
              if(mutation.equals(end)) {
                nextToEnds.add(node);
                continue;
              }
    
              if(!dict.contains(mutation))
                continue;
    
              if(depths.get(mutation) != null) {
                if(depths.get(mutation) < depth)
                  continue;
              } else
                depths.put(mutation, depth);
    
              Set<String> mutationParents = parents.get(mutation);
              if(mutationParents == null) {
                mutationParents = new HashSet<>();
                parents.put(mutation, mutationParents);
              }
              mutationParents.add(node);
    
              nodeQueue.add(mutation);
            }
          }
        }
    
        parents.put(end, nextToEnds);
    
        return traceBack(end, start, parents);
      }
    
      private List<List<String>> traceBack(String start, String end, Map<String, Set<String>> links) {
        List<List<String>> results = new ArrayList<>();
        if(start.equals(end)) {
          List<String> result = new ArrayList<>();
          result.add(end);
          results.add(result);
        } else {
          Set<String> parents = links.get(start);
          for(String parent : parents) {
            List<List<String>> subTraces = traceBack(parent, end, links);
            for(List<String> subTrace : subTraces) {
              List<String> result = new ArrayList<>();
              result.addAll(subTrace);
              result.add(start);
              results.add(result);
            }
          }
        }
        return results;
      }

Log in to reply
 

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