動機

原本就直接用trie，但看了別的解答才發現可以看長度來區分再直接比!!

重點是這樣居然比較快!! (in Py)

Problem

Design a data structure that supports adding new words and finding if a string matches any previously added string.

Implement the WordDictionary class:

  • WordDictionary() Initializes the object.
  • void addWord(word) Adds word to the data structure, it can be matched later.
  • bool search(word) Returns true if there is any string in the data structure that matches word or false otherwise. word may contain dots '.' where dots can be matched with any letter.

 

Example:

Input[WordDictionary,addWord,addWord,addWord,search,search,search,search][[],[bad],[dad],[mad],[pad],[bad],[.ad],[b..]]Output[null,null,null,null,false,true,true,true]ExplanationWordDictionary wordDictionary = new WordDictionary();wordDictionary.addWord(bad);wordDictionary.addWord(dad);wordDictionary.addWord(mad);wordDictionary.search(pad); // return FalsewordDictionary.search(bad); // return TruewordDictionary.search(.ad); // return TruewordDictionary.search(b..); // return True

 

Constraints:

  • 1 <= word.length <= 500
  • word in addWord consists lower-case English letters.
  • word in search consist of  '.' or lower-case English letters.
  • At most 50000 calls will be made to addWord and search.

Sol

用trie與dfs

def dfs(word,trie):
    tmp = trie
    for i in range(len(word)):
        if word[i] == ".":
            for k in tmp[1].keys():
                if dfs(word[i+1:],tmp[1][k]):
                    return True
            return False
        elif word[i] in tmp[1]:
            tmp = tmp[1][word[i]]
        else:
            return False
    return tmp[0]
class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.trie = [False, {}]

    def addWord(self, word: str) -> None:
        tmp = self.trie
        for c in word:
            if c not in tmp[1]:
                tmp[1][c] = [False, {}]
            tmp = tmp[1][c]
        tmp[0] = True

    def search(self, word: str) -> bool:
        return dfs(word,self.trie)

case study

把同長度的單字放在一起，之後就直接比

這樣在python居然比較快!?

class WordDictionary:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.d = defaultdict(set)

    def addWord(self, word: str) -> None:
        self.d[len(word)].add(word)
        

    def search(self, word: str) -> bool:
        s = self.d[len(word)]

        if '.' not in word:
            return word in s

        def match(a, b):
            for i in range(len(a)):
                if a[i] != '.' and a[i] != b[i]:
                    # word not match
                    return False
            return True

        for w in s:
            if match(word, w):
                return True

        return False