Word ladder is to find the number of steps to convert one string to another by changing one letter at a time. The intermediate words should be valid and can be found in pre-defined dictionary. The intuitive solution is using breadth first search (BFS). It starts from the original word, and changes one letter at a time, keeps doing until it finds the target word. A better solution of word ladder is using Bi-directional BFS.
Bidirectional BFS starts from both original word and target word. The search can meet in the middle. It cuts the search time by half. In the implementation, we maintain two sets startSet and endSet. The startSet holds all words changed from the original word, with one character change at a time. The endSet holds all words from the target word. Initially they only hold the original word and the target word respectively.
In the loop, we check each word in the startSet. Change one character at a time to create a new word next. Check whether the next is in the endSet. If not, first check whether this word is a valid word in the dictionary. If it is, check whether the word had been used before by using variable visited. visited guarantees that intermediate words occur once. If not, add it to the startSet, and start the next round of checking. If the next is in the endSet, the target is found. We reach the goal and the program returns.
The time complexity of BFS without memoization is O(b^d). b is branch factor, d is distance from start to end. Bidirectional BFS improves time complexity of BFS to O(b^(d/2)). So the time complexity is still exponential. In word ladder using bidirectional BFS, due to variable visited used for memoization, the time complexity is O(s*n). s is the word length. n is number of steps. The time complexity is quadratic. This is better than exponential.
Amazon Interview Question:
Given two strings s and t, and a dictionary D, transform s to t by changing one letter at a time, Each transformed word must exist in the dictionary. Find the length of shortest transformation. Return 0 if there is no such transformation sequence.
Example
Input: s = “cat”, t = “dog”, dictionary = [“cat”, “bat”, “bet”, “bot”, “bog”, “dog”]
Output: 5, As one shortest transformation is [cat->bat-> bot-> bog-> dog]
Java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | import java.util.*; public class WordLadder { //Bi-directional BFS + memoization, Time O(s*d), Space O(s*d), //s is string length, d is number of steps public static int wordLadderLength(String s, String t, List<String> wordList) { if (!wordList.contains(t)) return 0; Set<String> dict = new HashSet<>(wordList); Set<String> start = new HashSet<>(); Set<String> end = new HashSet<>(); Set<String> visited = new HashSet<>(); //works as memoization start.add(s); end.add(t); int step = 1; while (!start.isEmpty() && !end.isEmpty()) { if (start.size() > end.size()) { //start always has smaller set Set<String> tmp = start; start = end; end = tmp; } Set<String> tmp = new HashSet<>(); for (String word : start) { char[] ch = word.toCharArray(); for (int i = 0; i < ch.length; i++) { for (char c = 'a'; c <= 'z'; c++) { //constant time char origC = ch[i]; ch[i] = c; //replace c with all other letters in alphabet String next = String.valueOf(ch); if (end.contains(next)) return step + 1; if (!visited.contains(next) && dict.contains(next)) { tmp.add(next); visited.add(next); } ch[i] = origC; } } } start = tmp; step++; } return 0; } public static void main(String args[]) { List<String> words = Arrays.asList("cat", "bat", "bet", "bot", "bog", "dog" ); String s = "cat"; String t = "dog"; System.out.println("Dictinary: " + words); System.out.println("Start: '" + s + "', end: '" + t + "'"); System.out.println("Length of word ladder: " + wordLadderLength(s, t, words));; System.out.println(); } } |
JavaScript
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 | //Bi-directional BFS + memoization, Time O(s*d), Space O(s*d), //s is string length, d is number of steps function wordLadder(src, target, wordList) { if (!wordList.includes(target)) return 0; var dict = new Set(wordList); var start = new Set(); var end = new Set(); var visited = new Set(); //works as memoization start.add(src); end.add(target); var step = 1; while (start.size > 0 && end.size > 0) { if (start.size > end.size) { //start always has smaller set let tmp = start; start = end; end = tmp; } var tmp = new Set(); for (let word of start) { let ch = Array.from(word); //variations of word for (let i = 0; i < ch.length; i++) { for (let c = 'a'.charCodeAt(); c <= 'z'.charCodeAt(); c++) { //constant time let origC = ch[i]; ch[i] = String.fromCharCode(c); //replace c with all other letters in alphabet let next = ch.join(""); if (end.has(next)) return step + 1; if (!visited.has(next) && dict.has(next)) { tmp.add(next); visited.add(next); } ch[i] = origC; } } } console.log(tmp); start = tmp; step++; } return 0; } var words = ["cat", "bat", "bet", "bot", "bog", "dog" ]; var s = "cat"; var t = "dog"; console.log("Dictinary: " + words); console.log("Start: '" + s + "', end: '" + t + "'"); console.log("Length of word ladder: " + wordLadder(s, t, words)); |
Python
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 | import string #Bi-directional BFS + memoization, Time O(s*d), Space O(s*d), #s is string length, d is number of steps def wordLadder(s, t, wordList) : if t not in wordList: return 0 dict = set(wordList) start = set() end = set() visited = set(); #works as memoization start.add(s) end.add(t) step = 1; letters = list(string.ascii_lowercase) while len(start) > 0 and len(end) > 0 : if len(start) > len(end): #start always has smaller set tmp = start start = end end = tmp tmp = set() for word in start: ch = list(word) for i in range(0, len(ch)): for c in letters : #constant time origC = ch[i]; ch[i] = c #replace c with all other letters in alphabet next = ''.join(ch) if next in end: return step + 1 if next not in visited and next in dict: tmp.add(next) visited.add(next) ch[i] = origC print(tmp) start = tmp step +=1 return 0 words = ["cat", "bat", "bet", "bot", "bog", "dog" ] s = "cat" t = "dog" print( words) print("Start: '" + s + "', end: '" + t + "'") print("Length of word ladder: " + str(wordLadder(s, t, words))) |
Output:
Dictinary: [cat, bat, bet, bot, bog, dog]
Start: ‘cat’, end: ‘dog’
[bat, cat]
[bog, dog]
[bot]
Length of word ladder: 5
O Notation:
Time complexity: O(s * d)
Space complexity: O(s *d) for storing the intermediate data
s is average string length, d is number of steps.
Download WordLadder.java
Download WordLadder.js
Download WordLadder.py
