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.
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.