Amazon Onsite
Anonymous User
1150
Interview

Recently had an Amazon onsite and didn't know how to solve this question.

Given a list of strings, a starting word, and an ending word, return the list containing the minimum number of strings to reach the end word from the start word where each consecutive string differs by one letter to its prev.

ex.
Start: "heal"
End: "tall"
List: ["heal" "teal", "tall", "tell", "fall", "fell"]

2 possible paths
"heal", "teal", "tell" "tall" - return this one
"heal", "teal", "tell", "fell", "fall", "tall"

Edit: Attempted on my own by constructing a graph and using a recursive backtracking solution.

    static List<List<String>> paths = new ArrayList<>();
    static HashSet<String> used = new HashSet<>();
    // construct an adjacency map
    static HashMap<String, List<String>> adjMap = new HashMap<>();

    public static List<String> minPath(List<String> list, String start, String end){
        for(String key : list){
            adjMap.put(key, new ArrayList<>());
            for(String word : list){
                if(!key.equals(word) && isValid(key, word)){
                    adjMap.get(key).add(word);
                }
            }
        }

        // backtrack
        List<String> curr = new ArrayList<>();
        curr.add(start);
        used.add(start);
        backtrack(adjMap.get(start), end, curr);

        List<String> fewest = null;
        for(List<String> path : paths){
            if(fewest == null || path.size() < fewest.size()){
                fewest = path;
            }
        }

        return fewest;
    }

    public static void backtrack(List<String> neighbors, String end, List<String> curr){
        if(curr.size() > 0 && curr.get(curr.size() - 1).equals(end)) {
            paths.add(new ArrayList<>(curr));
            return;
        }

        String last = curr.get(curr.size() - 1);
        for(String neighbor : adjMap.get(last)){
            if(!used.contains(neighbor)){
                used.add(neighbor);
                curr.add(neighbor);

                backtrack(adjMap.get(neighbor), end, curr);

                used.remove(neighbor);
                curr.remove(curr.size() - 1);
            }
        }
    }

    public static boolean isValid(String s1, String s2){
        if(s1.length() != s2.length()){
            return false;
        }

        int n = s1.length();
        int diffs = 0;

        for(int i = 0; i < n; i++){
            if(s1.charAt(i) != s2.charAt(i)) {
                if (diffs >= 1)
                    return false;
                diffs++;
            }
        }
        return true;
    }
Comments (3)