LeetCode - 745. Prefix and Suffix Search

 

🔗 745. Prefix and Suffix Search

 

 

📌오늘의 학습 키워드

• 오늘 갑자기 난이도가 높아졌다. 시간 초과 문제를 잘 다뤄야 했는데 역시 hash(dictionary)로 해결했다. 

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

• 각각의 항목을 직접 확인하기 보다는 모든 경우의 수를 dictionary 에 두고 마지막에 확인해야 시간 초과가 일어나지 않았다.

📚오늘의 회고

• 어떤 문제가 있었고, 나는 어떤 시도를 했는지
  • 단순하게 for문에서 startswith, endswith로 확인하려고 했으나 실패했다.
• 어떻게 해결했는지
  • 가능한 prefix, suffix dictionary를 다 만들어 놓고 거기에서 찾았다.
• 무엇을 새롭게 알았는지
  • 마지막에 검색하기보다 모든 경우의 수를 만들어 놓고 검색하는게 더 빠를 수 있구나!

[🤓문제 해결 코드]

class WordFilter:

    def __init__(self, words):
        self.words = words
        self.dict = {}
        for idx, w in enumerate(words):
            for i in range(len(w) + 1):
                for j in range(len(w) - 1, -1, -1):
                    if w[:i] and w[j:]:
                        self.dict[w[:i] + "|" + w[j:]] = idx

    def f(self, pref: str, suff: str):
        if (pref + "|" + suff) not in self.dict:
            return -1
        return self.dict[pref + "|" + suff]