Trie with bidirectional BFS as alternative


  • 0
    C

    After the bidirectional BFS solution I thought a trie based solution could be inspiring. In that the trie nodes that represent words will as well represent the nodes in the graph for the BFS and carry flags to signal they were visited by BFS starting from startWord and endWord.
    The adjacent words can be found by looking into the trie and accepting one wrong character. Traversing the trie and marking the visited nodes can be done in one pass per BFS step.
    The algorithm, of course, takes long to create the trie but might be interesting if the same dictionary was used for several queries AKA ladderLength(). Besides its length it has a certain beauty :-)

    The trie looks like

       private static class TrieItem {
            String Word = null; // to signal a word, for simplicity
            boolean[] Visit = new boolean[2]; //0: coming from start, 1: coming from end
            TrieItem[] Next = new TrieItem[26];
    
            void add(String word);
            TrieItem getNext(char c);
            //...
        }
    

    Finding adjacent words and identifying if the two BFS frontiers meet would then look like:

        private static boolean findSimilarAndVisit(TrieItem ti, String wordToFind, 
                      int frontierId /*:0 start, 1: end */, List<String> nextWords) {
            class StackItem {
                int Index;
                boolean CanChangeOne;
                TrieItem TrieItem;
                // ...
            }
    
            int n = wordToFind.length();
            Stack<StackItem> s = new Stack<>();
            s.push(new StackItem(0, true, ti));
            while(!s.empty()) {
                StackItem si = s.pop();
                if (si.Index == n) {
                    if (!si.CanChangeOne && (si.TrieItem.Word != null) && !si.TrieItem.Visit[frontierId]) {
                        if (si.TrieItem.Visit[frontierId ^ 1]) return true; // visited with both frontiers
                        si.TrieItem.Visit[frontierId] = true; // mark as visited
                        nextWords.add(si.TrieItem.Word); // add to next words
                    }
                    continue;
                }
                char currentChar = wordToFind.charAt(si.Index);
                TrieItem next = si.TrieItem.getNext(currentChar);
                if (next != null) {
                    s.push(new StackItem(si.Index + 1, si.CanChangeOne, next));
                }
                if (si.CanChangeOne) {
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == currentChar) continue;
                        next = si.TrieItem.getNext(c);
                        if (next != null)
                            s.push(new StackItem(si.Index + 1, false, next));
                    }
                }
            }
            return false;
        }
    

    And embedded in the whole algorithm with corner cases removed:

        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            TrieItem trie = new TrieItem();
            for(String word : wordList) trie.add(word); // create trie
    
            int distance = 1; 
            int frontierId = 0; // 0: from beginWord, 1: from endWord
            LinkedList<String> q = new LinkedList<>(Arrays.asList(beginWord, null, endWord, null)); 
            while(q.size() > 2) {
                String current = q.poll();
                if(current == null) { 
                    q.add(null);
                    distance++;
                    frontierId ^= 1;
                } else if(findSimilarAndVisit(trie, current, frontierId, q)) {
                    return distance + 1; // since sequence length is asked
                }
            }
            return 0;
        }
    

    The complete Java8 source

        private static final int ALPHABET_FIRST_CHAR = 'a';
        private static final int ALPHABET_LAST_CHAR = 'z';
        private static final int ALPHABET_SIZE = ALPHABET_LAST_CHAR - ALPHABET_FIRST_CHAR + 1;
    
        private static class TrieItem {
            String Word = null; // a little memory overhead for convenience
            boolean[] Visit = new boolean[2]; //0: coming from start, 1: coming from end
            TrieItem[] Next = new TrieItem[ALPHABET_SIZE];
    
            void add(String word) {
                TrieItem ti = this;
                for(int i = 0; i < word.length(); i++) {
                    ti = ti.getOrAddNext(word.charAt(i));
                }
                ti.Word = word;
            }
    
            TrieItem getNext(char c) {
                return Next[c - ALPHABET_FIRST_CHAR];
            }
    
            TrieItem find(String word) {
                TrieItem ti = this;
                for(int i = 0; ti != null && i < word.length(); i++) {
                    ti = ti.getNext(word.charAt(i));
                }
                return ti;
            }
    
            TrieItem getOrAddNext(char c) {
                int i = c - ALPHABET_FIRST_CHAR;
                TrieItem ti = Next[i];
                if(ti != null) return ti;
                ti = new TrieItem();
                Next[i] = ti;
                return ti;
            }
        }
    
        private static boolean findExactAndVisit(TrieItem ti, String wordToFind, int frontierId) {
            ti = ti.find(wordToFind);
            if(ti != null) ti.Visit[frontierId] = true;
            return ti != null;
        }
    
        private static boolean findSimilarAndVisit(TrieItem ti, String wordToFind, int frontierId,
                                                   List<String> nextWords) {
            class StackItem {
                int Index;
                boolean CanChangeOne;
                TrieItem TrieItem;
                StackItem(int index, boolean canChangeOne, TrieItem trieItem) {
                    Index = index;
                    CanChangeOne = canChangeOne;
                    TrieItem = trieItem;
                }
            }
    
            int n = wordToFind.length();
            Stack<StackItem> s = new Stack<>();
            s.push(new StackItem(0, true, ti));
            while(!s.empty()) {
                StackItem si = s.pop();
                if (si.Index == n) {
                    if (!si.CanChangeOne && (si.TrieItem.Word != null) && !si.TrieItem.Visit[frontierId]) {
                        if (si.TrieItem.Visit[frontierId ^ 1]) return true; // visited with both frontiers
                        si.TrieItem.Visit[frontierId] = true; // mark as visited
                        nextWords.add(si.TrieItem.Word); // add to next words
                    }
                    continue;
                }
                char currentChar = wordToFind.charAt(si.Index);
                TrieItem next = si.TrieItem.getNext(currentChar);
                if (next != null) {
                    s.push(new StackItem(si.Index + 1, si.CanChangeOne, next));
                }
                if (si.CanChangeOne) {
                    for (char c = ALPHABET_FIRST_CHAR; c <= ALPHABET_LAST_CHAR; c++) {
                        if (c == currentChar) continue;
                        next = si.TrieItem.getNext(c);
                        if (next != null)
                            s.push(new StackItem(si.Index + 1, false, next));
                    }
                }
            }
            return false;
        }
    
    
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
            if(endWord == null || beginWord == null) return 0;
    
            TrieItem trie = new TrieItem();
            for(String word : wordList) trie.add(word); // create trie
    
            int distance = 1; // minimal distance if start and end are not equal (sequence length = distance + 1)
            int frontierId = 0; // 0: from beginWord, 1: from endWord
            LinkedList<String> q = new LinkedList<>(Arrays.asList(beginWord, null, endWord, null)); // queue
            findExactAndVisit(trie, beginWord, 0); // visit start word if present
            if(!findExactAndVisit(trie, endWord, 1)) return 0; // end word is not in wordList
            if(endWord.equals(beginWord)) return 1; // special case, end = start and end is in wordList
            while(q.size() > 2) {
                String current = q.poll();
                if(current == null) { // marks end of frontier, start and end alternate
                    q.add(null);
                    distance++;
                    frontierId ^= 1;
                } else if(findSimilarAndVisit(trie, current, frontierId, q)) {
                    return distance + 1; // since sequence length is asked
                }
            }
            return 0;
        }
    

Log in to reply
 

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