# Trie with bidirectional BFS as alternative

• 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];

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
}
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) {
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.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
}
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