The solution’s stated time complexity is O(nm^2). Is it actually O(nm)?
- The outer while loop runs until the queue is empty.
- In the worst case, all words in the list are visited, so the loop runs for O(n) iterations.
- Inside the loop, for each word, we generate all possible variations by changing one character at a time.
- For each character position, we try all 26 lowercase English characters.
- So, for each word, we generate O(m * 26) variations.
- The total time complexity is O(n * m * 26) = O(nm).
The solution’s stated space complexity is O(n). Is it actually O(nm)?
- The queue and myset store at most n words at any given time.
- Each word takes O(m) space.
Course: Grokking Coding Interview Patterns in Python - AI-Powered Learning for Developers
Lesson: https://www.educative.io/courses/grokking-coding-interview-patterns-python/solution-word-ladder