FilesExpand file tree

 master

/

implement-magic-dictionary.py

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

75 lines (62 loc) · 2.56 KB

 master

/

implement-magic-dictionary.py

Copy path

Top

File metadata and controls

• Code
• Blame

75 lines (62 loc) · 2.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

# Time: O(n), n is the length of the word

# Space: O(d)

# Implement a magic directory with buildDict, and search methods.

#

# For the method buildDict, you'll be given a list of non-repetitive words to build a dictionary.

#

# For the method search, you'll be given a word, and judge whether

# if you modify exactly one character into another character in this word,

# the modified word is in the dictionary you just built.

#

# Example 1:

# Input: buildDict(["hello", "leetcode"]), Output: Null

# Input: search("hello"), Output: False

# Input: search("hhllo"), Output: True

# Input: search("hell"), Output: False

# Input: search("leetcoded"), Output: False

# Note:

# You may assume that all the inputs are consist of lowercase letters a-z.

# For contest purpose, the test data is rather small by now.

# You could think about highly efficient algorithm after the contest.

# Please remember to RESET your class variables declared in class MagicDictionary,

# as static/class variables are persisted across multiple test cases. Please see here for more details.

class MagicDictionary(object):

def __init__(self):

"""

Initialize your data structure here.

"""

_trie = lambda: collections.defaultdict(_trie)

self.trie = _trie()

def buildDict(self, dict):

"""

Build a dictionary through a list of words

:type dict: List[str]

:rtype: void

"""

for s in dict:

curr = self.trie

for c in s:

curr = curr[c]

curr.setdefault("_end")

def search(self, word):

"""

Returns if there is any word in the trie that equals to the given word after modifying exactly one character

:type word: str

:rtype: bool

"""

def find(word, curr, i, mistakeAllowed):

if i == len(word):

return "_end" in curr and not mistakeAllowed

if word[i] not in curr:

return any(find(word, curr[c], i+1, False) for c in curr if c != "_end") \

if mistakeAllowed else False

if mistakeAllowed:

return find(word, curr[word[i]], i+1, True) or \

any(find(word, curr[c], i+1, False) \

for c in curr if c not in ("_end", word[i]))

return find(word, curr[word[i]], i+1, False)

return find(word, self.trie, 0, True)

# Your MagicDictionary object will be instantiated and called as such:

# obj = MagicDictionary()

# obj.buildDict(dict)

# param_2 = obj.search(word)