[Trie][Medium] 1268. Search Suggestions System

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

LeetCode - The World's Leading Online Programming Learning Platform

 

Q. searchWord를 입력함에 따라, products 중에서 이름이 겹치는 순서대로 제시어를 출력하라. 

   이때 제시어는 최대 3개가 되게 할 것이며, 각 제시어는 lexicorgraphically 하게 정렬하라. 

 

Solution.

 제시어가 입력됨에 따라, 해당 제시어와 겹치는 이름을 products name중에서 골라내면 된다. 다만, trie 자료 구조의 취지에 맞게, 제시어가 늘어감에 따라 매번 재검색을 하지 않고, 단어당 검색을 하고 연관이 없으로 바로 검색 대상에서 제외를 하여 재검색을 피한다. 

 나머지는 trie의 기본 구조와 같다.  

 

 위 내용을 뼈대로 코드를 작성해 본다. 

 

vector<vector<string>> suggestedProducts(vector<string>& products, string searchWord) 
{
    vector<vector<string>> vRet;

    // 문자 vector를 먼저 정렬한다.
    sort(products.begin(), products.end());
    for (int k = 0; k < searchWord.size(); ++k)
    {
        vector<string> vOut;
        vector<string>::iterator it = products.begin(); 
        for ( ; it != products.end(); )
        {
            // 현재 대상 character와 맞지 않는 product 이름은 바로 검색 목록에서 제외한다.
            if ((*it)[k] != searchWord[k])
                it = products.erase(it);
            else
            {
                if(vOut.size() < 3) vOut.push_back(*it);
                ++it;
            }
        }
        vRet.push_back(vOut);
    }
    return vRet;
}

 

 

Trie의 idea 대로 로직을 작성하면 큰 문제가 없는 문제.