[leetcode, medium] Search Suggestions System

Given an array of strings products and a string searchWord. We want to 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 the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return 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"]]

Example 3:

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags" Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

Example 4:

Input: products = ["havana"], searchWord = "tatiana" Output: [[],[],[],[],[],[],[]]

 

Constraints:

• 1 <= products.length <= 1000
• There are no repeated elements in products.
• 1 <= Σ products[i].length <= 2 * 10^4
• All characters of products[i] are lower-case English letters.
• 1 <= searchWord.length <= 1000
• All characters of searchWord are lower-case English letters.

문제 요약

products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"

이런 상품들과 찾고자하는 단어 mouse가 있을때 m만 입력했을때 미리보기 최대3개 mo만 입력했을때 미리보기 최대3개 ... 를 구하는 문제다.

 

m일때는 5개 상품 전부다 일치하지만 최대3개의 단어들만 사전순으로 뽑아야 하므로 mobile moneypot monitor 3개가 나와야한다.

 

Output: [ ["mobile","moneypot","monitor"], ["mobile","moneypot","monitor"], ["mouse","mousepad"], ["mouse","mousepad"], ["mouse","mousepad"] ]

 

/**
 * @param {string[]} products
 * @param {string} searchWord
 * @return {string[][]}
 */
var suggestedProducts = function(products, searchWord) {
    
    const sortedProducts = products.sort();
    const sortedProductChunks = sortedProducts.map((product,index) => {
        const s = new Set();
        let chunk = '';
        for(let i=0; i<product.length; i++) {
            chunk += product[i];
            s.add(chunk);
        }
        return s;
    });
    
    let wordChunk = '';
    const result = Array.from(Array(searchWord.length), () => new Array());
    
    for(let i=0; i<searchWord.length; i++) {
        wordChunk += searchWord[i];
        for(let j=0; j<sortedProducts.length; j++) {
            if(result[i].length >= 3) break;
            
            if(sortedProductChunks[j].has(wordChunk)) {
                result[i].push(sortedProducts[j]);   
            }
        }
    }
    
    return result;
};

먼저 사전순으로 결과를 출력해야 하므로 정렬을 해주고

정렬된 상품들에 대해서 나올 수 있는 모든 케이스를 셋에 넣어준다.

 

그리고 나서 searchWord를 순회하면서 아까 만들어둔 셋이랑 비교해가며 답을 만들었다.