Share My Java Solution


  • 0
    Z
    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            LinkedHashMap<String, List<List<String>>> frontier = new LinkedHashMap<>();
            wordList.add(endWord);
            List<String> beginFrontierList = new ArrayList<>();
            beginFrontierList.add(beginWord);
            List<List<String>> starterList = new ArrayList<List<String>>();
            starterList.add(beginFrontierList);
            frontier.put(beginWord, starterList);
            Queue<String> currentKeyList;
            boolean endWordReached = false;
            while (!frontier.isEmpty()) {
                if (endWordReached == true) { break; }
                currentKeyList = new LinkedList<>(frontier.keySet());
                String key;      // Current starting string
                char[] keyChArr; // Current starting string as list
                String mutated;  // Mutated string with one letter diff
                while (currentKeyList.size() > 0) {
                    key = currentKeyList.poll();
                    for (int i = 0; i < key.length(); i++) {
                        for (char ch = 'a'; ch <= 'z'; ch++) {
                            keyChArr = key.toCharArray();
                            keyChArr[i] = ch;
                            mutated = String.valueOf(keyChArr);
                            if (wordList.contains(mutated) && !mutated.equals(key)) {
                                List<List<String>> previousPaths = frontier.get(key);
                                List<List<String>> appendedPaths = new ArrayList<>();
                                for (List<String> ls: previousPaths) {
                                    List<String> newList = new ArrayList<>(ls);
                                    newList.add(mutated);
                                    appendedPaths.add(newList);
                                }
                                if (!frontier.containsKey(mutated)) {
                                    frontier.put(mutated, appendedPaths);
                                } else {
                                    frontier.get(mutated).addAll(appendedPaths);
                                } 
                                if (mutated.equals(endWord)) {
                                    endWordReached = true;
                                } 
                            }
                        }
                    }
                    wordList.remove(key);
                    if (!key.equals(endWord)) {
                        frontier.remove(key);
                    } 
                }
                wordList.removeAll(frontier.keySet());
            }
            List<List<String>> ret = frontier.get(endWord);
            if (ret == null) { return new ArrayList<List<String>>(); }
            else { return ret; }
        }
    }
    

Log in to reply
 

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