How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a Medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Reddit.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Reddit during technical interviews.

Find word sequence with 1–2 char changes

Company: Reddit

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Technical Screen

Given a beginWord, an endWord, and a dictionary (wordList) of unique same-length lowercase words, determine whether there exists a transformation sequence from beginWord to endWord such that each step changes exactly 1 or 2 characters (substitutions only; no insertions or deletions) and every intermediate word is in the dictionary. If such a path exists, return one shortest path as a list of words; otherwise return an empty list. Implement an efficient solution, justify BFS vs. DFS choices, analyze time/space complexity, and discuss optimizations for large dictionaries and handling cases where beginWord is not in the dictionary.

Quick Answer: This question evaluates graph traversal and shortest-path search skills, specifically reasoning about BFS vs DFS, string transformation modeling, and algorithmic time/space complexity within the Coding & Algorithms domain.

Given a beginWord, an endWord, and a dictionary wordList of unique lowercase words, return one shortest transformation sequence from beginWord to endWord. In a single move, you may change exactly 1 or exactly 2 character positions, using substitutions only. Every word strictly between the first and last word must appear in wordList. beginWord does not need to be in the dictionary, and endWord may be outside the dictionary as long as it is the final word in the path. If multiple shortest paths exist, return any one of them. If no valid path exists, return an empty list. Because every move has equal cost, this is a shortest-path problem in an unweighted graph, so BFS is the right traversal to use instead of DFS.

Constraints

0 <= len(wordList) <= 5000
1 <= len(beginWord) == len(endWord) <= 10
All words in wordList are unique, lowercase, and the same length as beginWord

Examples

Input: ("hit", "cog", ["hot", "dot", "dog", "lot", "log"])

Expected Output: ["hit", "hot", "cog"]

Explanation: 'hot' differs by 1 from 'hit', and 'cog' differs by 2 from 'hot'. No 1-step path exists because 'hit' and 'cog' differ in 3 positions.

Input: ("aaaa", "bbbb", ["aabb"])

Expected Output: ["aaaa", "aabb", "bbbb"]

Explanation: 'aaaa' -> 'aabb' changes the last two positions, then 'aabb' -> 'bbbb' changes the first two.

Input: ("same", "same", ["came", "lame"])

Expected Output: ["same"]

Explanation: The start already equals the target, so the shortest sequence contains only that word.

Input: ("aaa", "bbb", ["aac", "acc", "ccc"])

Expected Output: []

Explanation: You can reach some dictionary words, but none lead to 'bbb' by a sequence of 1- or 2-character substitutions.

Input: ("abc", "abd", [])

Expected Output: ["abc", "abd"]

Explanation: 'abd' is one substitution away from 'abc', and the final word is allowed to be outside the dictionary.

Solution

def solution(beginWord, endWord, wordList):
    from collections import defaultdict, deque

    if beginWord == endWord:
        return [beginWord]
    if len(beginWord) != len(endWord):
        return []

    L = len(beginWord)

    words = []
    seen = set()
    for w in wordList:
        if len(w) == L and w not in seen:
            words.append(w)
            seen.add(w)

    if endWord not in seen:
        words.append(endWord)
        seen.add(endWord)

    def hamming_at_most_two(a, b):
        diff = 0
        for x, y in zip(a, b):
            if x != y:
                diff += 1
                if diff > 2:
                    return diff
        return diff

    one_map = defaultdict(list)
    two_map = defaultdict(list)

    for w in words:
        for i in range(L):
            one_map[w[:i] + '*' + w[i + 1:]].append(w)
        for i in range(L):
            for j in range(i + 1, L):
                two_map[w[:i] + '*' + w[i + 1:j] + '*' + w[j + 1:]].append(w)

    queue = deque([beginWord])
    visited = {beginWord}
    parent = {beginWord: None}

    def build_path(last):
        path = []
        while last is not None:
            path.append(last)
            last = parent[last]
        return path[::-1]

    while queue:
        word = queue.popleft()

        for i in range(L):
            pattern = word[:i] + '*' + word[i + 1:]
            for nxt in one_map.pop(pattern, []):
                if nxt not in visited and hamming_at_most_two(word, nxt) in (1, 2):
                    visited.add(nxt)
                    parent[nxt] = word
                    if nxt == endWord:
                        return build_path(nxt)
                    queue.append(nxt)

        for i in range(L):
            for j in range(i + 1, L):
                pattern = word[:i] + '*' + word[i + 1:j] + '*' + word[j + 1:]
                for nxt in two_map.pop(pattern, []):
                    if nxt not in visited and hamming_at_most_two(word, nxt) in (1, 2):
                        visited.add(nxt)
                        parent[nxt] = word
                        if nxt == endWord:
                            return build_path(nxt)
                        queue.append(nxt)

    return []

Time complexity: O(N * L^2), where N is the number of usable same-length words (including endWord) and L is the word length. Space complexity: O(N * L^2).

Hints

Model each word as a node in an unweighted graph. If you need the shortest path, BFS is usually the right traversal.
Avoid comparing every pair of words. Instead, group words by patterns created by replacing 1 or 2 positions with a wildcard so neighbors can be found quickly.

Quick Overview

This question evaluates graph traversal and shortest-path search skills, specifically reasoning about BFS vs DFS, string transformation modeling, and algorithmic time/space complexity within the Coding & Algorithms domain.