LeetCode 솔루션

[6/18] 745. Prefix and Suffix Search

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.06.18 23:22

5,984 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

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.

#Google, #Apple, #Amazon, #Facebook, #String, #Design, #Trie

링크

https://leetcode.com/problems/prefix-and-suffix-search/ 1303 회 연결

익명
작성일 2022.06.19 22:11

# 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)

[code=Python 3]# 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)[/code]