Reduction to level order traversal with annotation


  • 0
    L

    I always prefer a reduction to simpler algorithm template, and for this problem it's a level order traversal of the word mutation graph.

    public class Solution {
    	public List<List<String>> findLadders(String start, String end, Set<String> dict) {
    		dict.add(start);
    		dict.add(end);
    
    		Map<String, List<String>> myPrevs = new HashMap<>(); // for tracking path
    		Map<String, Integer> visited = new HashMap<>(); // also remembers word's least depth
    		Deque<String> curr = new ArrayDeque<>(); // use two rolling queues
    		Deque<String> next = new ArrayDeque<>();
    
    		int lvl = 0;
    		curr.offer(start);
    		visited.put(start, lvl); // starts at 0
    		myPrevs.put(start, Arrays.asList((String) null)); // use a dummy Prev for bfs termination
    		boolean found = false; // when becomes true, we no longer process endWord's row
    		while (!curr.isEmpty()) {
    			String word = curr.poll();
    
    			for (int i = 0; i < word.length(); i++) {
    				StringBuilder sb = new StringBuilder(word);
    				for (char c = 'a'; c <= 'z'; c++) {
    					if (c == word.charAt(i)) // skip self match
    						continue;
    					sb.setCharAt(i, c);
    					String cand = sb.toString(); // generate the candidate
    					if (!dict.contains(cand))
    						continue;
    
    					if (!found && cand.equals(end))
    						found = true; // set only when firstly found
    
    					if (!visited.containsKey(cand)) { // normal traversal technique
    						next.offer(cand);
    						visited.put(cand, lvl + 1); // always firstly found on the next row
    					}
    
    					if (!myPrevs.containsKey(cand))
    						myPrevs.put(cand, new ArrayList<String>());
    					if (visited.get(cand) == lvl + 1) // Prevs of candidate must be from the same row
    						myPrevs.get(cand).add(word);
    				}
    			}
    
    			if (curr.isEmpty() && !found) { // if endWord found, no need to process endWord's row
    				curr = next; // normal level-wise traversal technique
    				next = new ArrayDeque<String>();
    				lvl++;
    			}
    		}
    
    		List<List<String>> col = new ArrayList<>();
    		if (!myPrevs.containsKey(end)) // not a single path leads to endWord
    			return col;
    		dfs(end, new ArrayList<String>(), col, myPrevs);
    
    		return col;
    	}
    
    	void dfs(String word, List<String> path, List<List<String>> collect, Map<String, List<String>> myPrevs) {
    		if (word == null) { // dummy Prev of startWord
    			List<String> copy = new ArrayList<>(path);
    			Collections.reverse(copy); // because a path starts from endWord
    			collect.add(copy);
    			return;
    		}
    
    		path.add(word);
    		for (String p : myPrevs.get(word)) {
    			dfs(p, path, collect, myPrevs);
    		}
    		path.remove(path.size() - 1); // plain back-tracking technique
    	}
    }

Log in to reply
 

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