Easy to understand Java BFS accepted with clear explanation


  • 0

    A slight modification of word ladder I. The idea is quite simple. Instead of removing visited words from wordDict, we use a map to record visited node and its level. We only allow same nodes to repeat at the same level. The shortest path set never contains two pathes with same node appearing at different levels, because otherwise there must be a shortcut and those two paths won't be of the same length. The class TreeNode is defined to help backtrack to its root through parent pointer. One word may appear twice at the same level, so we cannot use just a map or array to mark its parent. Same word may have multiple parents. BFS guarrantees an optimal solution and all solutions at the same level will be of the same length.
    That is why we keep searching until the end of level where we find the 1st solution.

    I don't know why the actually performance is less than 10% of all submissions. The time complexity is not bad. Can anybody optimize it?

    public class Solution {
        public List<List<String>> findLadders(String beginWord, String endWord, Set<String> wordList) {
            List<List<String>> list = new ArrayList<>();
            int level = 0;
            boolean found = false; // flag used to stop searching for the next level
            Queue<TreeNode> q = new LinkedList<>();
            Map<String, Integer> map = new HashMap<>(); // map records visited node and its level
            q.offer(new TreeNode(beginWord, null)); // beginWord is the root of tree, no parent
            map.put(beginWord, 0);
            while (!q.isEmpty()) {
                if (found)
                    return list;
                int size = q.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = q.poll();
                    String word = node.val;
                    if (word.equals(endWord)) {
                        found = true; // mark true so it will go on searching until the end of current level, so all paths are of the same length.
                        List<String> ladder = new ArrayList<>();
                        while (node != null) {
                            ladder.add(0, node.val);
                            node = node.parent;
                        }
                        list.add(ladder);
                    } else { // change character one at a time
                        char[] wordArray = word.toCharArray();
                        for (int j = 0; j < wordArray.length; j++) {
                            char c = wordArray[j];
                            for (char k = 'a'; k <= 'z'; k++) {
                                if (c != k) {
                                    wordArray[j] = k;
                                    String newWord = new String(wordArray);
                                    // if a visited node is at lower level, it won't be added again. Duplicate is allowed ONLY at same level
                                    if (wordList.contains(newWord) && (!map.containsKey(newWord) || map.get(newWord) == level)) {
                                        map.put(newWord, level);
                                        TreeNode child = new TreeNode(newWord, node);
                                        q.offer(child);
                                    }
                                }
                            }
                            wordArray[j] = c;//change it back before modifying next char
                        }
                    }
                }
                level++;
            }
            return list;// empty list
        }
        
        
    }
    
    class TreeNode {
        public String val;
        public TreeNode parent;
        public TreeNode(String v, TreeNode p) {
            val = v;
            parent = p;
        }
    }

  • 0
     } else  if (!found) { // change character one at a time
    

    I modifed the "else" in the middle so that once the 1st solution is found, we stop adding children. But it did not imprive the performance much.


  • 0
    B

    You don't have to iterate through all characters, you can just check the number of differing characters between the head of the queue and each word in the wordlist.


Log in to reply
 

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