動機

Hard題都是來看創意的

  1. 用pair讓兩個dfs整合在一起
  2. 把prefix與suffix encode成一個字串

Problem

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]ExplanationWordFilter 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.

Sol

兩個Trie配set intersection會超時?

那就上cache

class Trie:
    def __init__(self):
        self.next = defaultdict(Trie)
        self.idxs = set()
    def add(self,s,i):
        now = self
        while s:
            now = now.next[s[0]]
            s = s[1:]
        now.idxs.add(i)

    @cache
    def dfs(self,s):
        if s:
            if s[0] in self.next:
                return self.next[s[0]].dfs(s[1:])
            else:
                return set()
        elif not self.next:
            return self.idxs
        else:
            return self.idxs.union(*[self.next[c].dfs("") for c in self.next])
class WordFilter:

    def __init__(self, words: List[str]):
        self.forward = Trie()
        self.backward = Trie()
        
        for (i,s) in enumerate(words):
            self.forward.add(s,i)
            self.backward.add(s[::-1],i)
    @cache
    def f(self, prefix: str, suffix: str) -> int:
        #print(self.forward.dfs(prefix) , self.backward.dfs(suffix))
        return max(list(self.forward.dfs(prefix) & self.backward.dfs(suffix[::-1])),default=-1)

或是，把單字與reverse的單字合成pair，就可以同時看了

Trie = lambda: collections.defaultdict(Trie)
WEIGHT = False

class WordFilter(object):
    def __init__(self, words):
        self.trie = Trie()

        for weight, word in enumerate(words):
            cur = self.trie
            cur[WEIGHT] = weight
            for i, x in enumerate(word):
                #Put all prefixes and suffixes
                tmp = cur
                for letter in word[i:]:
                    tmp = tmp[letter, None]
                    tmp[WEIGHT] = weight

                tmp = cur
                for letter in word[:-i or None][::-1]:
                    tmp = tmp[None, letter]
                    tmp[WEIGHT] = weight

                #Advance letters
                cur = cur[x, word[~i]]
                cur[WEIGHT] = weight

    def search(self, prefix, suffix):
        cur = self.trie
        for a, b in map(None, prefix, suffix[::-1]):
            if (a, b) not in cur: return -1
            cur = cur[a, b]
        return cur[WEIGHT]

或是，把suffix放前面再把單字放後面，像

#apple，e#apple，el#apple，ple#apple，pple#apple，apple#apple

Trie = lambda: collections.defaultdict(Trie)
WEIGHT = False

class WordFilter(object):
    def __init__(self, words):
        self.trie = Trie()

        for weight, word in enumerate(words):
            word += '#'
            for i in xrange(len(word)):
                cur = self.trie
                cur[WEIGHT] = weight
                for j in xrange(i, 2 * len(word) - 1):
                    cur = cur[word[j % len(word)]]
                    cur[WEIGHT] = weight

    def f(self, prefix, suffix):
        cur = self.trie
        for letter in suffix + '#' + prefix:
            if letter not in cur:
                return -1
            cur = cur[letter]
        return cur[WEIGHT]