In the example, the words are all upper case while in the test case, they are all lower case.
Couldn’t you more easily determine adjacency of two words via a single for loop, checking to determine if the difference between the two strings is at most 1 character? All the string manipulation seems inefficient.
For TV’s soluton, you’re looking at (dictionary length * word length) checks, compared to (25 * word length) checks for the given solution. As such, by cancelling out word length from each equation, you’re left with dictionary length vs 25. Therefore, if dictionary length is under 25 then TV’s solution is better, but once it is over 25 then iterating over every possible word from the current word becomes more efficient. So for the given tests (and small dictionary sizes) TV’s solution is better by a small margin - whereas the margin between the two massively increases as the dictionary size increases. As such for real world use cases you would use the given solution due to the constant (25) time increases.
Thanks Subhra for pointing this out. Learning is VERY difficult when stuff like this is common.
The solution loops over all character mutations in every letter which is more exhaustive than required. We really just need to search for a word in the word_list. Here is my take for the get_nbr function:
def word_ladder(begin: str, end: str, word_list: List[str]) -> int:
def get_nbrs(word,word_list):
res = []
for i in range(len(word)):
prefix = word[:i]
letter = word[i]
suffix = word[i+1:]
prefix_match = [w.startswith(prefix) for w in word_list]
suffix_match = [w.endswith(suffix) for w in word_list]
for iw in range(len(word_list)):
if prefix_match[iw] and suffix_match[iw]:
res.append(word_list[iw])
return set(res)
The other script is almost identical to the previous ones in BFS.
Elegant solution!
from typing import List
from string import ascii_letters
from collections import deque
def word_ladder(begin: str, end: str, word_list: List[str]) → int:
# WRITE YOUR BRILLIANT CODE HERE
# - For each giving word get its neighbor
# - We can get neigbor by changing each charactere in the giving word.
# - keep in the queue the new_word that is in the given words_list
# - If neighbor/new_word is not in the giving words_list then skip/continue
# - If new word match the end_word, done and return the count of new words
# - Else if add the new_word to the queue and remove it from
# SET of lest of words (this same as marking it visited)
def get_neighbor(begin):
for i in range(len(begin)):
for c in ascii_letters:
yield begin[:i] + c + begin[i+1:]
def bfs(begin, end, word_list):
word_count = 0
set_word_list = set(word_list)
q = deque([begin])
while (len(q) > 0):
n = len(q)
#Need to count for the begin word
word_count += 1
for _ in range(n):
word = q.popleft()
for neighbor_word in get_neighbor(word):
if neighbor_word not in set_word_list:
continue
if neighbor_word == end:
return word_count
q.append(neighbor_word)
set_word_list.remove(neighbor_word)
return 0
return bfs(begin, end, word_list)
version with returning the list of words
from typing import List
from string import ascii_letters
from collections import deque
def word_ladder(begin: str, end: str, word_list: List[str]) → int:
# WRITE YOUR BRILLIANT CODE HERE
# - For each giving word get its neighbor
# - We can get neigbor by changing each charactere in the giving word.
# - keep in the queue the new_word that is in the given words_list
# - If neighbor/new_word is not in the giving words_list then skip/continue
# - If new word match the end_word, done and return the count of new words
# - Else if add the new_word to the queue and remove it from
# SET of lest of words (this same as marking it visited)
def get_neighbor(begin):
for i in range(len(begin)):
for c in ascii_letters:
yield begin[:i] + c + begin[i+1:]
def bfs(begin, end, word_list):
# res = []
word_count = 0
set_word_list = set(word_list)
q = deque([begin])
# res.append(begin)
while (len(q) > 0):
n = len(q)
#Need to count for the begin word
word_count += 1
for _ in range(n):
word = q.popleft()
for neighbor_word in get_neighbor(word):
if neighbor_word not in set_word_list:
continue
if neighbor_word == end:
return word_count
q.append(neighbor_word)
set_word_list.remove(neighbor_word)
# We can also return the wordsby returning res[]:
# res.apend(neighbor_word)
return 0
return bfs(begin, end, word_list)
def word_ladder(begin: str, end: str, word_list: List[str]) → int:
words = set(word_list)
def get_neighbors(word):
for i in range(len(word)):
for c in ascii_letters:
next_word = word[:i] + c + word[i+1:]
if next_word not in words:
continue
yield next_word
q = deque([begin])
steps = -1
while len(q) > 0:
steps += 1
for _ in range(len(q)):
next_word = q.popleft()
if next_word == end:
return steps
for neighbor in get_neighbors(next_word):
q.append(neighbor)
words.remove(neighbor)
return steps
please add case
hot
dog
hot dog
public static int wordLadder(String begin, String end, List<String> wordList) {
return bfs(begin, end, wordList);
}
private static int bfs(String begin, String end, List<String> wordList) {
ArrayDeque<String> queue = new ArrayDeque<>();
Set<String> visited = new HashSet<>();
queue.add(begin);
visited.add(begin);
int steps = 0;
while (queue.size() > 0) {
int n = queue.size();
for (int i = 0; i < n; i++) {
String current = queue.poll();
if(current.equals(end))
return steps;
for (String neighbor : getNeighbors(current, wordList)) {
if (visited.contains(neighbor))
continue;
visited.add(neighbor);
queue.add(neighbor);
}
}
steps++;
}
return -1;
}
private static List<String> getNeighbors(String current, List<String> wordList) {
List<String> result = new ArrayList<>();
int wordSize = current.length();
for (String word : wordList) {
if (word.trim().equals(""))
continue;
int diff = 0;
for (int i = 0; i < wordSize; i++) {
if (current.charAt(i) != word.charAt(i)) {
diff++;
}
if(diff > 1)
break;
}
if (diff == 1)
result.add(word);
}
return result;
}Structured Programming JS Solution:
function ladderLength(begin, end, wordList) {
let result = 0;
let count = 0;
const queue = [begin];
const visited = new Set(queue);
if (begin != end && wordList.includes(end)) {
while (queue.length && !result) {
count += 1;
const n = queue.length;
for (
let i = 0;
i < n && !result;
i++
) {
const word = queue.shift();
if (word === end) {
result = count;
} else {
for (const newWord of wordList) {
if (!visited.has(newWord) && isValidMove(word, newWord)) {
queue.push(newWord);
visited.add(newWord);
}
}
}
}
}
}
return result;
}
function isValidMove(initialWord, newWord) {
let count = 0;
for (let i = 0; i < initialWord.length && count < 2; i++) {
const a = initialWord.charAt(i);
const b = newWord.charAt(i);
if (a != b) {
count += 1;
}
}
return count === 1;
}
Faster Structured Programming JS Solution:
function ladderLength(begin, end, wordList) {
const alphabet = ["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"];
const words = new Set(wordList);
const queue = [begin];
let distance = 0;
let result = 0;
if (begin != end && words.has(end)) {
while (queue.length > 0 && !result) {
distance += 1;
const n = queue.length;
for (
let i = 0;
i < n && !result;
i++
) {
const word = queue.shift();
if (word === end) {
result = distance;
}
for (let j = 0; j < word.length; j++) {
for (const letter of alphabet) {
const next_word = word.slice(0, j) + letter + word.slice(j+1);
if (words.has(next_word)) {
queue.push(next_word);
words.delete(next_word);
}
}
}
}
}
}
return result;
}
My solution does not use an alphabet but a function to check if 2 words are “adjacent”.
bool is_next(const std::string& current, const std::string& next) {
int diff = 0;
for (int i = 0; i < current.length(); ++i) {
if (current[i] != next[i]) ++diff;
}
return diff == 1;
}
int word_ladder(std::string begin, std::string end, std::vector<std::string> word_list) {
if (begin == end) return 0;
int steps = 1;
std::set<std::string> visited;
std::queue<std::string> q;
q.push(begin);
while (q.size() > 0) {
int n = q.size();
for (int i = 0; i < n; ++i) {
std::string current = q.front();
for (const std::string& word : word_list) {
if (!visited.count(word) && is_next(current, word)) {
if (word == end) return steps;
q.push(word);
}
}
visited.emplace(current);
q.pop();
}
++steps;
}
return -1;
}
why not just check word match with the list of dictionary words?
To find the neighbors, we are creating random words each time which can take up to O(26^m) time where m is the length of the word with all 26 letter combinations for each letter of the word. Majority of the words are a waste as they may not be valid words in the first place. There must be a better way to find neighbors. Can you please elaborate on this?
Solution without yield or trying every letter in the alphabet:
def word_ladder(begin: str, end: str, word_list: List[str]) → int:
# WRITE YOUR BRILLIANT CODE HERE
def get_neighbours(node):
neighbours = []
for word in word_list:
diff = 0
for i in range(len(word)):
if word[i] != node[i]:
diff += 1
if diff == 1:
neighbours.append(word)
return neighbours
queue = deque([begin])
visited = set([begin])
steps = 0
while queue:
n = len(queue)
for _ in range(n):
node = queue.popleft()
if node == end:
return steps
for neighbour in get_neighbours(node):
if neighbour not in visited:
queue.append(neighbour)
visited.add(neighbour)
steps += 1
return steps
the Java solution misses handling for cases where begin == end
it’s O(26*m). alternatively you could loop through each word in the dictionary but that’s slow when the dictionary gets large.