[LeetCode 75] Medium - 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:

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]]:
        total_res = []
        products.sort()
        
        search_word = ''
        search_word_ln = 0
        for s_idx in range(len(searchWord)):
            res = []
            sub_word_cnt = 0
            for p in products:
                if p[:s_idx+1] == searchWord[:s_idx+1]:
                    sub_word_cnt +=1
                    res.append(p)
                if sub_word_cnt == 3:                    
                    break
            total_res.append(res)
        return total_res

 

이 코드는 이진 탐색을 사용하지 않고, 순차 탐색(Brute Force) 방식으로 해결한 풀이 임.

 

 

풀이 방법

 

이 문제는 이진 탐색 또는 Trie(트라이) 자료구조를 사용하여 효율적으로 해결할 수 있습니다. 두 가지 풀이를 각각 설명하겠습니다.

 

이진 탐색 기반 풀이

순차 탐색 vs 이진 탐색

 

Trie 기반 풀이

두 방법 중 이진 탐색이 구현이 간단하고, 이 문제에서 성능적으로도 충분히 적합 하다고 함 !!

 

제안 풀이 법: 이진 탐색(Two 포인터)

 

https://youtu.be/D4T2N0yAr20?si=HxJ_OVvM9Tx2S199

 

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        res = []  # 최종 결과를 저장할 리스트 (각 접두사에 대한 추천 리스트)
        products.sort()  # 제품 이름 리스트를 사전 순으로 정렬 (추천 리스트는 항상 사전 순으로 반환되므로 필수)

        # 검색 범위 초기화
        l, r = 0, len(products) - 1  # l: 검색 범위의 왼쪽 끝, r: 검색 범위의 오른쪽 끝

        # searchWord의 각 문자를 하나씩 처리하며 접두사를 확장
        for i in range(len(searchWord)):
            c = searchWord[i]  # 현재 처리 중인 문자 (searchWord[i])

            # 왼쪽 포인터를 이동하여 접두사가 일치하지 않는 제품들을 제외
            while l <= r and (len(products[l]) <= i or products[l][i] != c):
                # 조건 1: len(products[l]) <= i
                #   현재 제품의 길이가 검색어 접두사보다 짧은 경우 -> 접두사와 일치할 수 없음
                # 조건 2: products[l][i] != c
                #   현재 제품의 i번째 문자가 접두사의 i번째 문자와 일치하지 않음
                l += 1  # 왼쪽 포인터를 오른쪽으로 이동하여 검색 범위 좁힘

            # 오른쪽 포인터를 이동하여 접두사가 일치하지 않는 제품들을 제외
            while l <= r and (len(products[r]) <= i or products[r][i] != c):
                # 조건 1: len(products[r]) <= i
                #   현재 제품의 길이가 검색어 접두사보다 짧은 경우 -> 접두사와 일치할 수 없음
                # 조건 2: products[r][i] != c
                #   현재 제품의 i번째 문자가 접두사의 i번째 문자와 일치하지 않음
                r -= 1  # 오른쪽 포인터를 왼쪽으로 이동하여 검색 범위 좁힘

            # 현재 접두사로 시작하는 제품 리스트 초기화
            res.append([])  # 현재 접두사에 대한 추천 리스트 생성
            remain = r - l + 1  # 검색 범위 내 남아 있는 제품 수 계산

            # 검색 범위 내 최대 3개의 추천 제품을 추가
            for j in range(min(3, remain)):  # 최대 3개까지만 추천
                res[-1].append(products[l + j])  # 검색 범위 내의 앞쪽 제품을 추천 리스트에 추가

        return res  # 최종 결과 반환 (각 접두사에 대한 추천 리스트)

 

이 코드는 이진 탐색의 개념을 사용하여 접두사 검색 범위를 점점 좁혀 나가는 방식으로 동작함

 

 

 

두번째 시도: 또 순차 탐색으로 품

 

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()
        res = []

        for i in range(1, len(searchWord)+1):
            sub_res = []
            cnt = 0
            for product in products:
                if searchWord[:i] == product[:i]:
                    sub_res.append(product)
                    cnt += 1

                    if cnt == 3:
                        break
            res.append(sub_res)
        return res

 

이진탐색으로 풀수 있게, 연습하자!

 

class Solution:
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        # 제품 리스트를 사전순으로 정렬
        products.sort()
        l, r = 0, len(products) - 1  # 좌우 포인터 초기화
        res = []  # 결과를 저장할 리스트

        # searchWord의 접두사 길이만큼 반복
        for i in range(len(searchWord)):
            c = searchWord[i]  # 현재 접두사의 문자

            # 왼쪽 포인터 이동: 접두사 조건을 만족하지 않으면 이동
            while l <= r and (len(products[l]) < i + 1 or products[l][i] != c):
                l += 1

            # 오른쪽 포인터 이동: 접두사 조건을 만족하지 않으면 이동
            while l <= r and (len(products[r]) < i + 1 or products[r][i] != c):
                r -= 1

            # 현재 범위 내 최대 3개의 추천 제품 선택
            res.append([])
            for j in range(min(3, r - l + 1)):
                res[-1].append(products[l + j])

        return res