Problem statement

https://leetcode.com/problems/search-suggestions-system/

Solution

One way to solve this problem is tries, but I think it can be a bit overkill for medium difficulty quesion, so I prefer some other idea.

We can sort all our words and use two pointers idea. Then we add letter by letter from our word W (originally it was searchWord, I renamed it for more consice code) and adjust our searching range [beg, end]. If len(P[beg]) is less or equal to i, it means that word we have in current index of P is too short, so we need to more beg to the right. Also if we have P[beg][i] != c, it means that current index is not good either, so we need to move it to the right as well. Similar logic is done for end pointer.

In the end of each iteration we have the property, that words in range [beg, end] have the same i starting letter with W. So, we try to choose 3 words or less if it is not possible (it can be 0 words as well, if [beg, end] is empty.

Complexity

Let, m = len(W), n = len(P), L is the biggest lenght of words in P. Then for sort we need O(L * n * log n) time. Then we need O(n) time for two pointers approach: we make m steps to move our pointers, which one with O(1) complexity. Also on each of m steps for i we add at most 3 words to final answer and spend O(m*L) total time for it. So, final time complexity is O(L * n * log n + m * L). Space complexity is O(n*L).

Code

class Solution:
    def suggestedProducts(self, P, W):
        P.sort()
        beg, end, ans = 0, len(P) - 1, []

        for i, c in enumerate(W):
            while beg <= end and (len(P[beg]) <= i or P[beg][i] != c):
                beg += 1
                
            while beg <= end and (len(P[end]) <= i or P[end][i] != c):
                end -= 1
                
            ans.append(P[beg:min(end+1, beg+3)])

        return ans