Clear Java solution with a single BFS


  • 3
    I
    public class Solution {
    	public List<List<String>> findLadders(String endWord, String beginWord, Set<String> wordList) {
    		wordList.add(endWord);
    		Queue<Node> queue = new LinkedList<>();
    		Set<String> visited = new HashSet<>(), unvisited = new HashSet<>();
    		unvisited.addAll(wordList);
    		int level = 0, minDist = Integer.MAX_VALUE;
    		List<List<String>> result = new ArrayList<>();
    
    		queue.add(new Node(beginWord, null, 0));
    		visited.add(beginWord);
    
    		while (!queue.isEmpty()) {
    			Node current = queue.remove();
    			if (current.val.equals(endWord) && current.dist <= minDist) {
    				minDist = current.dist;
    				addPath(result, current);
    				continue;
    			}
    
    			if (current.dist > minDist) {
    				break;
    			}
    
    			if (current.dist > level) {
    				unvisited.removeAll(visited);
    				level = current.dist;
    			}
    
    			addNeighbours(queue, visited, unvisited, current);
    		}
    
    		return result;
    	}
    
    	private void addNeighbours(Queue<Node> queue, Set<String> visited, Set<String> unvisited, Node current) {
    		char[] chars = current.val.toCharArray();
    		for (int i = 0; i < chars.length; ++i) {
    			for (char c = 'a'; c <= 'z'; ++c) {
    				char tmp = chars[i];
    				chars[i] = c;
    				String nbr = new String(chars);
    				if (unvisited.contains(nbr)) {
    					queue.add(new Node(nbr, current, current.dist + 1));
    					visited.add(nbr);
    				}
    				chars[i] = tmp;
    			}
    		}
    	}
    
    	private void addPath(List<List<String>> result, Node current) {
    		List<String> path = new ArrayList<>(current.dist);
    		while (current != null) {
    			path.add(current.val);
    			current = current.parent;
    		}
    		result.add(path);
    	}
    
    	private class Node {
    		String val;
    		Node parent;
    		int dist;
    
    		private Node(String val, Node parent, int dist) {
    			this.val = val;
    			this.parent = parent;
    			this.dist = dist;
    		}
    	}
    }
    

  • 0
    D

    in general BFS, visited is added when each iteration. but you do that differently,
    what is the difference compared to the standard BFS?

                         if (current.dist > level) {
    				unvisited.removeAll(visited);
    				level = current.dist;
    			}
    
    

  • 0
    I

    @darren5 The difference is that in this task we want to find all shortest paths. This means that we might need to reuse some nodes and make sure that we don't prune paths that are still valid. Consider the following example:

                 sit
               /     \
            hit       sat - bat
               \     /
                 hat
    

    In this example the result is [ [hit, sit, sat, bat], [hit, hat, sat, bat] ].
    Let's say we go up from hit. From sit we can reach sat and the total path length will be 2. If we directly remove sat, we won't be able to reach it from hat. Thus, we need to make sure that we remove nodes when there is no shorter path that leads to them. That's why we have if (current.dist > level).


  • 0
    D

    @ivtoskov excellent!
    i've learned new technique in BFS. Thanks.


Log in to reply
 

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