LeetCode //C - 1268. Search Suggestions System

1268. Search Suggestions System

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:

Example 2:

Constraints:

• 1 <= products.length <= 1000
• 1 <= products[i].length <= 3000
• 1 < = s u m ( p r o d u c t s [ i ] . l e n g t h ) < = 2 ∗ 1 0 4 1 <= sum(products[i].length) <= 2 * 10^4 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.

From: LeetCode
Link: 1268. Search Suggestions System

---

Solution:

Ideas：

1. Sort the products lexicographically to ensure we can easily pick the top three suggestions.
2. Iterate through each character of searchWord, building the prefix to search in the sorted products.
3. Search for products that match the current prefix.
4. Store up to three matches for each prefix in the result list.
5. Allocate memory dynamically for the result and intermediate lists, making sure to follow C conventions for memory management.

Caode:

int cmp(const void* a, const void* b) {
    return strcmp(*(const char**)a, *(const char**)b);
}

char*** suggestedProducts(char** products, int productsSize, char* searchWord, int* returnSize, int** returnColumnSizes) {
    // Sort the products lexicographically
    qsort(products, productsSize, sizeof(char*), cmp);
    
    // Initialize the result array and sizes
    *returnSize = strlen(searchWord);
    char*** result = (char***)malloc(*returnSize * sizeof(char**));
    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));
    
    for (int i = 0; i < *returnSize; i++) {
        result[i] = (char**)malloc(3 * sizeof(char*)); // At most 3 suggestions
        int count = 0; // Count of suggestions for this prefix
        for (int j = 0; j < productsSize && count < 3; j++) {
            if (strncmp(products[j], searchWord, i + 1) == 0) {
                result[i][count++] = products[j];
            }
        }
        (*returnColumnSizes)[i] = count; // Set the actual number of suggestions for this prefix
    }
    
    return result;
}