educative.io

Complexity of Word Search

Courses
,
#1

On line 23: if depth_first_search(row + rowOffset, col + colOffset, word[1:], grid):

word[1:] creates a new substring of word, which takes O(l) time and occupies O(l) space within our stack frame, which means our time and space complexities are higher than those provided. We can address this by passing our word index rather than creating a substring in each frame.

Course: Grokking Coding Interview Patterns in Python - Learn Interactively
Lesson: Solution: Word Search - Grokking Coding Interview Patterns in Python

1 Like
#2

Hello @Isaac_Haseley,

That is actually a very good observation. Yes indeed the slicing operation in Python code is creating a new list internally which in result will increase the time and space complexity analysis of the code. Just as you suggested, instead of a substring, we can pass the index as a parameter, in this way, we can keep the mentioned time and space complexity as correct.

1 Like