Java solution with BFS


  • 0
    J
     public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        if (beginWord.length() != endWord.length()) return result;
        Set<String> level = new HashSet<>();
        level.add(beginWord);
        Set<String> seen = new HashSet<>();
        ArrayList<Map<String, Set<String>>> neighbors = new ArrayList<>();
        while (!level.isEmpty()) {
          Set<String> nextLevel = new HashSet<>();
          boolean found = false;
          Map<String, Set<String>> levelNeighbors = new HashMap<>();
          seen.addAll(level);
          neighbors.add(levelNeighbors);
    
          for (String word : level) {
            char[] cs = word.toCharArray();
            for (int i = 0; i < cs.length; i++) {
              for (char c = 'a'; c <= 'z'; c++) {
                if (c == cs[i]) continue;
                char tmp = cs[i];
                cs[i] = c;
                String step = new String(cs);
                if (wordList.contains(step) && !seen.contains(step)) {
                  Set<String> endPoints = levelNeighbors.get(step);
                  if (endPoints == null) {
                    endPoints = new HashSet<>();
                    levelNeighbors.put(step, endPoints);
                  }
                  endPoints.add(word);
                  nextLevel.add(step);
                  if (step.equals(endWord)) {
                    found = true;
                  }
                }
                cs[i] = tmp;
              }
            }
          }
          if (!found) level = nextLevel;
          else {
            List<String> revPath = new ArrayList<>();
            revPath.add(endWord);
            backTrace(beginWord, endWord, neighbors, neighbors.size() - 1, revPath, result);
            break;
          }
        }
        return result;
      }
    
      private void backTrace(String beginWord, String endWord,
          ArrayList<Map<String, Set<String>>> neighbors, int start, List<String> path, List<List<String>> result) {
        if (start < 0) {
          if (endWord.equals(beginWord)) {
            List<String> r = new ArrayList<>();
            for (int i = path.size() - 1; i >= 0; i--) {
              r.add(path.get(i));
            }
            result.add(r);
          }
          return;
        }
        Map<String, Set<String>> steps = neighbors.get(start);
        Set<String> nextLevel = steps.get(endWord);
        if (nextLevel == null) return;
        for (String s : nextLevel) {
          path.add(s);
          backTrace(beginWord, s, neighbors, start - 1, path, result);
          path.remove(path.size() - 1);
        }
      }
    

Log in to reply
 

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