Dictionary Nomad - Amazon Top Interview Questions
Problem Statement :
You are given a list of strings dictionary and two strings start and end. You want to reach from start to end by modifying one character at a time and making sure each resulting word is also in the dictionary. Words are case-sensitive. Return the minimum number of steps it would take to reach end. Return -1 if it's not possible. Constraints 0 ≤ n * m ≤ 300,000 where n is the length of dictionary and m is the length of the longest string Example 1 Input dictionary = ["day", "say", "soy"] start = "soy" end = "day" Output 3 Explanation We can take this path: ["soy", "say", "day"]. Example 2 Input dictionary = ["day", "soy"] start = "soy" end = "day" Output -1 Explanation There's no way to change 1 character to reach "day".
Solution :
Solution in C++ :
int solve(vector<string>& dictionary, string start, string end) {
unordered_set<string> seen{start}, dict(dictionary.begin(), dictionary.end());
queue<string> q{{start}};
int steps = 0;
while (!q.empty()) {
int sz = q.size();
steps++;
while (sz-- > 0) {
auto& p = q.front();
if (p == end) return steps;
q.pop();
for (int i = 0; i < p.size(); i++) {
char old = p[i];
for (char c = 'a'; c <= 'z'; c++) {
p[i] = c;
if (dict.count(p) && !seen.count(p)) {
seen.insert(p);
q.push(p);
}
}
p[i] = old;
}
}
}
return -1;
}
Solution in Java :
import java.util.*;
class Solution {
public int solve(String[] dictionary, String start, String end) {
Set<String> dict = new HashSet<>();
for (String d : dictionary) dict.add(d);
Set<String> visited = new HashSet<>();
Deque<String> q = new ArrayDeque<>();
q.add(start);
int steps = 0;
while (!q.isEmpty()) {
steps++;
int sz = q.size();
for (int i = 0; i < sz; i++) {
String cur = q.remove();
if (visited.contains(cur))
continue;
visited.add(cur);
if (cur.equals(end))
return steps;
// try to generate all possible strings for next level
for (int j = 0; j < cur.length(); j++) {
// for each possition, we try [a-z] chars
for (char c = 'a'; c <= 'z'; c++) {
String newstr =
cur.substring(0, j) + c + cur.substring(j + 1, cur.length());
if (dict.contains(newstr))
q.offer(newstr);
}
}
}
}
return -1;
}
}
/*
build a bi directional graph, node u and v will have an edge if u and v have only
one character difference
add start and end too in graph
find shorted path to reach from start to end using bfs then
challenge: how to build graph efficiently?
*/
Solution in Python :
class Solution:
def solve(self, dictionary, start, end):
words, visited = set(dictionary), set()
q = deque()
q.append(start)
level = 1
while len(q) > 0:
size = len(q)
for i in range(size):
cur = q.popleft()
if cur == end:
return level
for idx in range(len(cur)):
for c in range(97, 97 + 26):
new_word = cur[:idx] + chr(c) + cur[idx + 1 :]
if new_word not in visited and new_word in words:
q.append(new_word)
visited.add(new_word)
level += 1
return -1
View More Similar Problems
Minimum Average Waiting Time
Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h
View Solution →Merging Communities
People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w
View Solution →Components in a graph
There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu
View Solution →Kundu and Tree
Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that
View Solution →Super Maximum Cost Queries
Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and
View Solution →Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →