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

[6/18] 745. Prefix and Suffix Search

컨텐츠 정보

본문

Hard
1901446Add to ListShare

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)
전체 396 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 180 명
  • 오늘 방문자 3,392 명
  • 어제 방문자 5,332 명
  • 최대 방문자 11,134 명
  • 전체 회원수 1,048 명
알림 0