Word Ladder

LeetCode Q 127 - Word Ladder

Given two words (beginWord and endWord), and a dictionary’s word list, find the length of shortest transformation sequence from beginWord to endWord, such that:

1. Only one letter can be changed at a time.
2. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Note:

• Return 0 if there is no such transformation sequence.
• All words have the same length.
• All words contain only lowercase alphabetic characters.
• You may assume no duplicates in the word list.
• You may assume beginWord and endWord are non-empty and are not the same.

Example 1:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"] Output: 5
Explanation: As one shortest transformation is “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
return its length 5.

Example 2:
Input: beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"] Output: 0
Explanation: The endWord “cog” is not in wordList, therefore no possible transformation.

Solution : BFS / Two-End BFS (Bidirectional Search)

Solution 1: BFS

Two tips to avoid TLE:

1. Use set instead of list
2. Remove word in the set once we add it to the queue.

Code:

public int ladderLength(String start, String end, List<String> 
words) {
	Set<String> wordList = new HashSet<>(words);

	if (!wordList.contains(end)) return 0;
	if (start.equals(end)) return 1;
	
	Queue<String> que = new LinkedList<>();
	que.offer(start); visited.add(start);

	int level = 1;
	while (!que.isEmpty()) {
		int size = que.size();
		while (size-- != 0) {
			String curr = que.poll();

			for (int i = 0; i < curr.length(); i++) {
				char[] chs = curr.toCharArray();
				for (char ch = 'a'; ch <= 'z'; ch++) {
					chs[i] = ch;
					String next = String.valueOf(chs);
					if (next.equals(end)) return level + 1;
					if (wordList.contains(next)) {
						que.offer(next);
						wordList.remove(next);
					}
				}
			}
		}
		level++;
	}

	return 0;
}

Solution 2: Two-End BFS (Bidirectional Search)

Code:

public int ladderLength(String start, String end, List<String> 
wordList) {
	if (!wordList.contains(end)) return 0;
	if (start.equals(end)) return 1;
	
	Queue<String> queA = new LinkedList<>();
	Set<String> visitedA = new HashSet<>();
	queA.offer(start); visitedA.add(start);

	Queue<String> queB = new LinkedList<>();
	Set<String> visitedB = new HashSet<>();
	queB.offer(end); visitedB.add(end);

	Queue<String> que = null;
	Set<String> setCurr = null, setOp = null;

	int level = 1;
	while (!queA.isEmpty() && !queB.isEmpty()) {
		if (queA.size() <= queB.size()) {
			que = queA; setCurr = visitedA; setOp = visitedB;
		} else {
			que = queB; setCurr = visitedB; setOp = visitedA;
		}

		int size = que.size();
		while (size-- != 0) {
			String word = que.poll();

			List<String> nextList = getNext(word, wordDict);

			for (String next: nextList) {
				if (setOp.contains(next)) return level;

				if (!setCurr.contains(next)) {
					que.offer(next); setCurr.add(next);
				}
			}
		}
		level++;
	}

	return 0;
}

private List<String> getNext(String curr, List<String> dict) {
	List<String> res = new ArrayList<>();
	
	for (int i = 0; i < curr.length(); i++) {
		char[] chs = curr.toCharArray();
		for (char c = 'a'; c <= 'z'; ++c) {
			if (c != old) {
				String next = String.valueOf(chs);
				if (dict.contains(next)) 
					res.add(next);
			}
		}
	}
	
	return res;
}

Two-End BFS (Bidirectional Search)

Bidirectional search is a graph search algorithm which find smallest path form source to goal vertex. It runs two simultaneous search, i.e.

1. Forward search form source/initial vertex toward goal vertex
2. Backward search form goal/target vertex toward source vertex

Bidirectional search replaces single search graph(which is likely to grow exponentially) with two smaller sub graphs – one starting from initial vertex and other starting from goal vertex. The search terminates when two graphs intersect.

Why Two-End BFS?

Because in many cases it is faster, it dramatically reduce the amount of required exploration.
Suppose if branching factor of tree is b and distance of goal vertex from source is d, then the normal BFS/DFS searching complexity would be O(b^d). On the other hand, if we execute two search operation then the complexity would be O(b^(d/2)) for each search and total complexity would be O(b^(d/2)+b^(d/2)) which is far less than O(b^d).

When to use bidirectional approach?

We can consider bidirectional approach when

• Both initial and goal states are unique and completely defined.
• The branching factor is exactly the same in both directions.

Performance measures

Time and Space Complexity : Time and space complexity is O(b^{d/2})