Java Solution with Iteration


  • 14
    A

    Code is about 40 lines, put explanation in comments.

    /**
     * we are essentially building a graph, from start, BF.
     * and at each level we find all reachable words from parent.
     * we stop if the current level contains end,
     * we return any path whose last node is end.
     * 
     * to achieve BFT, use a deuqe;
     * a key improvement is to remove all the words we already reached
     * in PREVIOUS LEVEL; we don't need to try visit them again
     * in subsequent level, that is guaranteed to be non-optimal solution.
     * at each new level, we will removeAll() words reached in previous level from dict.
     */
    public List<List<String>> findLadders(String start, String end, Set<String> dict) {
        List<List<String>> results = new ArrayList<List<String>>();
        dict.add(end);
        // instead of storing words we are at, we store the paths.
        Deque<List<String>> paths = new LinkedList<List<String>>();
        List<String> path0 = new LinkedList<String>();
        path0.add(start);
        paths.add(path0);
        // if we found a path ending at 'end', we will set lastLevel,
        // use this data to stop iterating further.
        int level = 1, lastLevel = Integer.MAX_VALUE;
        Set<String> wordsPerLevel = new HashSet<String>();
        while (!paths.isEmpty()) {
            List<String> path = paths.pollFirst();
            if (path.size() > level) {
                dict.removeAll(wordsPerLevel);
                wordsPerLevel.clear();
                level = path.size();
                if (level > lastLevel)
                    break; // stop and return
            }
            //  try to find next word to reach, continuing from the path
            String last = path.get(level - 1);
            char[] chars = last.toCharArray();
            for (int index = 0; index < last.length(); index++) {
                char original = chars[index];
                for (char c = 'a'; c <= 'z'; c++) {
                    chars[index] = c;
                    String next = new String(chars);
                    if (dict.contains(next)) {
                        wordsPerLevel.add(next);
                        List<String> nextPath = new LinkedList<String>(path);
                        nextPath.add(next);
                        if (next.equals(end)) {
                            results.add(nextPath);
                            lastLevel = level; // curr level is the last level
                        } else
                            paths.addLast(nextPath);
                    }
                }
                chars[index] = original;
            }
        }
        
        return results;
    }

  • 0
    S

    Thank you for sharing. I learn from your code and modified my own and achieve 1000 ms.
    My previous algorithm was 1400+ms


  • 1

    I have a similar iteration solution (traditional BFS) here, short but slow.

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            List<List<String>> out = new ArrayList<List<String>>();
            if (beginWord == null || endWord == null || wordList == null || wordList.size() < 1) {
                return out;
            }
            Set<String> set = new HashSet<String>();
            for (String word : wordList) {
                set.add(word);
            }
            if (!set.contains(endWord)) {
                return out;
            }
            Queue<List<String>> q = new LinkedList<List<String>>();
            q.offer(Arrays.asList(beginWord));
            boolean find = false;
            while (!q.isEmpty() && !find) {
                int size = q.size();
                Set<String> toDelete = new HashSet<String>();
                while (size-- > 0) {
                    List<String> path = new ArrayList<String>(q.poll());
                    char[] curr = path.get(path.size()-1).toCharArray();
                    for (int i = 0; i < curr.length; ++i) {
                        char backup = curr[i];
                        for (char c = 'a'; c <= 'z'; ++c) {
                            curr[i] = c;
                            String next = new String(curr);
                            if (set.contains(next)) {
                                path.add(next);
                                q.offer(new ArrayList<String>(path));
                                if (next.equals(endWord)) {
                                    out.add(new ArrayList<String>(path));
                                    find = true;
                                }
                                path.remove(path.size()-1);
                                toDelete.add(next);
                            }
                        }
                        curr[i] = backup;
                    }
                }
                for (String word : toDelete) {
                    if (set.contains(word)) {
                        set.remove(word);
                    }
                }
            }
            return out;
        }
    }
    

Log in to reply
 

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