Dictionary Nomad - Amazon Top Interview Questions

                        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