엔지니어 게시판
LeetCode 솔루션 분류

# [6/18] 745. Prefix and Suffix Search

• mingki 작성
• 작성일

• 65 조회
• 1 댓글

### 본문

Hard

Design a special dictionary with some words that searchs 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 prefix, string suffix)` Returns the index of the word in the dictionary, which has the prefix `prefix` and the suffix `suffix`. 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 <= 15000`
• `1 <= words[i].length <= 10`
• `1 <= prefix.length, suffix.length <= 10`
• `words[i]``prefix` and `suffix` consist of lower-case English letters only.
• At most `15000` calls will be made to the function `f`.

댓글 1

## 학부유학생님의 댓글

• 학부유학생
• 작성일
``````# N: # of words L: avg length of words M: avg length of pref + suff
# Time to make Trie O(N*L^2) | search: O(M)
# Space: O(N*L^2)

class WordFilter:

def __init__(self, words: List[str]):
self.trie = {}
self.idx_mark = '@'

for idx, word in enumerate(words):
word +='#'
length = len(word)
word += word
for i in range(length):
curr_trie = self.trie
curr_trie[self.idx_mark] = idx
for char in word[i:]:
if char not in curr_trie:
curr_trie[char] = {}
curr_trie = curr_trie[char]
curr_trie[self.idx_mark] = idx
def f(self, prefix: str, suffix: str) -> int:

curr_trie = self.trie
for char in suffix+"#"+prefix:
if char not in curr_trie: return -1
curr_trie = curr_trie[char]

return curr_trie[self.idx_mark]

# *******Trial 1: TLE******
# import collections
# class TrieNode:
#     def __init__(self, char):
#         self.char = char
#         self.next = {}
#         self.idxs = []
# class WordFilter:

#     def __init__(self, words: List[str]):
#         self.pref = TrieNode("")
#         self.suff = TrieNode("")
#         for idx, word in enumerate(words):
#             self.create_trie(word, idx, self.pref)
#             self.create_trie(word[::-1], idx, self.suff)

#     def f(self, prefix: str, suffix: str) -> int:
#         pref_idxs, suff_idxs = self.find_idxlist(prefix, self.pref), self.find_idxlist(suffix[::-1], self.suff)
#         if not pref_idxs or not suff_idxs: return -1

#         pref, suff = pref_idxs.pop(), suff_idxs.pop()
#         while pref_idxs or suff_idxs:
#             if pref == suff: return pref
#             if not suff_idxs or (pref_idxs and pref>suff): pref = pref_idxs.pop()
#             else: suff = suff_idxs.pop()

#         return pref

#     def create_trie(self, word, idx, trie):
#         for char in word:
#             if char not in trie.next:
#                 trie.next[char] = TrieNode(char)
#             trie = trie.next[char]
#             trie.idxs.append(idx)

#     def find_idxlist(self, pref_or_suff, trie):
#         for char in pref_or_suff:
#             if char not in trie.next:
#                 return None
#             trie = trie.next[char]

#         return trie.idxs.copy()

# Your WordFilter object will be instantiated and called as such:
# obj = WordFilter(words)
# param_1 = obj.f(prefix,suffix)``````
전체 128 / 1 페이지

### 새댓글

• 등록자 JakeMinSVK 등록일 18:25
• 등록자 JakeMinSVK 등록일 18:24
• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20

### Stats

• 현재 접속자 74 명
• 오늘 방문자 652 명
• 어제 방문자 683 명
• 최대 방문자 1,262 명
• 전체 회원수 264 명