문제

1268. Search Suggestions System
      User Accepted:1720
      User Tried:2026
      Total Accepted:1765
      Total Submissions:4342
      Difficulty:Medium
      You are given an array of strings products and a string searchWord.

Design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return a list of lists of the suggested products after each character of searchWord is typed.

Example 1:
  Input: products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
  Output: [["mobile","moneypot","monitor"],["mobile","moneypot","monitor"],["mouse","mousepad"],["mouse","mousepad"],["mouse","mousepad"]]
  Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
  After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
  After typing mou, mous and mouse the system suggests ["mouse","mousepad"].

Example 2:
  Input: products = ["havana"], searchWord = "havana"
  Output: [["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
  Explanation: The only word "havana" will be always suggested while typing the search word.
 

Constraints:
  1 <= products.length <= 1000
  1 <= products[i].length <= 3000
  1 <= sum(products[i].length) <= 2 * 104
  All the strings of products are unique.
  products[i] consists of lowercase English letters.
  1 <= searchWord.length <= 1000
  searchWord consists of lowercase English letters.

풀이

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        answer = []
        suggestion = []
        key_word_list = []
        #사전순서로 정렬
        products.sort()
        
        for i in range(len(searchWord)):
            key_word_list.append(searchWord[i])
            for j in range(len(products)):
                product_list = list(products[j])
                if key_word_list == product_list[:i+1]:
                    if len(suggestion) < 3:
                        suggestion.append("".join(product_list))
                        
            answer.append(suggestion)
            suggestion = []
        return answer

뭔가 획기적으로 시간 복잡도를 줄이는 방법은 생각해내지 못했고, 문제에서 제시한 조건을 그대로 구현하는 게 고작이었다.