Back to course home
0% completed
Vote For New Content
Time complexity should be O(N*K), where K is the length of the longest word
Bruno Ely
Jan 11, 2024
String comparison is not a constant-time operation, so the loop that runs O(N) times is doing O(K) work every time. This matters because you could have a list of words in the order of tens or hundreds of words, but words in the order of thousands of characters since it wasn't specified that "words" must actually be English words and can't be full books, for instance.
1
0
Comments
Comments
Miguel 2 years ago
I had the same thought 👍🏽
A
Alexey a year ago
This problem has very specific constraints, including:1 <= words[i].length <= 10
The max word length is 10 chars, so the time to compare 2 words of the max length is capped by a constant number C. Therefore, time complexity is O(CN) = O(N).