LeetCode 솔루션 분류
[6/18] 745. Prefix and Suffix Search
본문
Hard
1901446Add to ListShareDesign 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 thewords
in the dictionary.f(string prefix, string suffix)
Returns the index of the word in the dictionary, which has the prefixprefix
and the suffixsuffix
. 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
andsuffix
consist of lower-case English letters only.- At most
15000
calls will be made to the functionf
.
관련자료
-
링크
댓글 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)