공부한 내용 본인의 언어로 정리하기

리트코드#745. Prefix and Suffix Search

문제 설명

WordFilter라는 클래스를 설계해야 합니다. 이 클래스는 주어진 단어 목록에서 특정 접두사(prefix)와 접미사(suffix)를 가진 단어를 효율적으로 찾을 수 있어야 합니다. 문제의 요구 사항은 다음과 같습니다:

WordFilter(string[] words):

단어 목록 words를 입력받아 객체를 초기화합니다.
f(string pref, string suff):

pref로 시작하고 suff로 끝나는 단어의 인덱스를 반환합니다.
여러 개의 단어가 조건을 만족할 경우, 가장 큰 인덱스를 반환합니다.
조건을 만족하는 단어가 없으면 -1을 반환합니다.

어떤 문제가 있었고, 나는 어떤 시도를 했는지

• 솔직히 리트코드는 처음이라 완전 손도 못대고 있었다. 다른 분들의 코드를 봤는데 이해하기 어려워써, 이번에는 리트코드에서는 어떤식으로 작성을 해야하는지 감만 잡고 가자~ 는 느낌으로 제출하였다

class WordFilter:
    def __init__(self, words):
        self.prefix_suffix_map = {}
        
        # 각 단어 처리
        for index, word in enumerate(words):
            prefix = ""
            # 모든 가능한 접두사 생성
            for i in range(len(word) + 1):
                suffix = ""
                # 모든 가능한 접미사 생성
                for j in range(len(word) + 1):
                    self.prefix_suffix_map[(word[:i], word[j:])] = index

    def f(self, pref, suff):
        # 해시 맵에서 인덱스 검색, 없으면 -1 반환
        return self.prefix_suffix_map.get((pref, suff), -1)

• 문제 자체의 경우에는 접두사와 접미사를 탐색하는 문제였다

• 전처리단계
  - 목록의 각 단어를 순회합니다.
  - 각 단어에 대해 모든 가능한 접두사와 접미사를 생성합니다. 길이가 n인 단어의 경우 n+1개의 접두사(빈 접두사 포함)와 n+1개의 접미사가 있습니다.
  - 각 접두사와 접미사 조합에 대해 단어의 인덱스를 해시 맵에 저장합니다.

• 검색
  - 검색을 수행할 때, 단순히 (접두사, 접미사) 쌍을 해시 맵에서 찾아 해당 인덱스를 반환합니다.
  

무엇을 새롭게 알았는지

• 리트 코드 작성시에 class 와 제공해주는 가이드라인 코드는 수정 가능
• 딕셔너리를 사용하여 각 조합에 대한 인덱스를 저장하는 방식 (딕셔너리의 key를 생성해서 value 로 index 를 저장하는 것이 인상적)

학습할 것은 무엇인지

안하고싶어여..