Java BFS approach


  • 2
    M
    /* Used a distance map to keep track of the ladder length */
    
    public class Solution {
        public int ladderLength(String beginWord, String endWord, Set<String> wordList) {
    		wordList.add(endWord);
    		Queue<String> queue = new LinkedList<String>();
    		Map<String, Integer> dist = new HashMap<String, Integer>();
    		
    		dist.put(beginWord, 1);
    		queue.add(beginWord);
    		
    		while (!queue.isEmpty()) {
    			String str = queue.poll();
    			if (str.equals(endWord)) {
    				return dist.get(str);
    			}
    			StringBuilder current = new StringBuilder(str);
    			for (int i = 0; i < current.length(); i++) {
    				char original = current.charAt(i);
    				for (char c = 'a'; c <= 'z'; c++) {
    				    if (c != current.charAt(i)) {
        					current.setCharAt(i, c);
        					String mutated = current.toString();
        					if (!dist.containsKey(mutated) && wordList.contains(mutated)) {
        						queue.add(mutated);
        						dist.put(mutated, dist.get(str) + 1);
        					}
    				    }
    				}
    				current.setCharAt(i, original);
    			}
    		}
            return 0;
        }
    }

Log in to reply
 

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