Introduction

In this blog post, we will explore how to solve the LeetCode problem "1268" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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.

Explanation

• Sort Products: Sort the products array lexicographically to easily find the smallest matching products.
  • Iterate and Filter: Iterate through each prefix of searchWord. For each prefix, filter the sorted products array to keep only the products that start with that prefix.
  • Limit Suggestions: From the filtered products, take the first three (or fewer if there are fewer than three matches) to ensure we return at most three suggestions.

• Runtime Complexity: O(n log n + m*k*len), where n is the number of products, k is the average length of product strings, len is the length of searchWord, and m is the number of products that share the common prefix. Storage Complexity: O(n), primarily due to storing the sorted products list.

Code

    def suggestedProducts(products, searchWord):
    products.sort()
    result = []
    for i in range(1, len(searchWord) + 1):
        prefix = searchWord[:i]
        suggestions = []
        for product in products:
            if product.startswith(prefix):
                suggestions.append(product)
        result.append(suggestions[:3])
    return result