[99클럽 코테 스터디 15일차 TIL] Prefix and Suffix Search

문제

https://leetcode.com/problems/prefix-and-suffix-search/description/

Prefix and Suffix Search

Design a special dictionary that searches the words in it by a prefix and a suffix.

Implement the WordFilter class:

• WordFilter(string[] words) Initializes the object with the words in the dictionary.
• f(string pref, string suff) Returns the index of the word in the dictionary, which has the prefix pref and the suffix suff. If there is more than one valid index, return the largest of them. If there is no such word in the dictionary, return 1.

Example 1:

Input
["WordFilter", "f"]
[[["apple"]], ["a", "e"]]
Output
[null, 0]
Explanation
WordFilter wordFilter = new WordFilter(["apple"]);
wordFilter.f("a", "e"); // return 0, because the word at index 0 has prefix = "a" and suffix = "e".

Constraints:

• 1 <= words.length <= 104
• 1 <= words[i].length <= 7
• 1 <= pref.length, suff.length <= 7
• words[i], pref and suff consist of lowercase English letters only.
• At most 104 calls will be made to the function f.

 

키워드

• 완전탐색

 

해결 방법

풀이

class WordFilter(object):

    def __init__(self, words):
        """
        :type words: List[str]
        """
        self.prefix_suffix_map = {}
        # 주어진 단어 리스트 words를 순회하면서 각 단어의 모든 접두사와 접미사 조합을 구합니다.
        # 각 접두사와 접미사 조합에 해당하는 단어의 인덱스를 prefix_suffix_map 딕셔너리에 저장합니다.
        # 예를 들어, "apple"이라는 단어가 있다면 ("a", "e"), ("ap", "le"), ("app", "ple") 등의 조합이 저장됩니다.
        for index, word in enumerate(words):
            length = len(word)
            for i in range(length + 1):
                for j in range(length + 1):
                    prefix = word[:i]
                    suffix = word[j:]
                    self.prefix_suffix_map[(prefix, suffix)] = index

    def f(self, pref, suff):
        """
        :type pref: str
        :type suff: str
        :rtype: int
        """
        # prefix_suffix_map 딕셔너리에서 주어진 접두사와 접미사 조합에 해당하는 인덱스를 찾습니다.
        # 해당 조합이 존재하면 그 인덱스를 반환하고, 존재하지 않으면 -1을 반환합니다.
        return self.prefix_suffix_map.get((pref, suff), -1)

# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(pref,suff)