Skip to main content

Leetcode 211. Design Add and Search Words Data Structure. Python (Prefix Tree)

 

211. Design Add and Search Words Data Structure


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]

Explanation
WordDictionary wordDictionary = new WordDictionary();
wordDictionary.addWord("bad");
wordDictionary.addWord("dad");
wordDictionary.addWord("mad");
wordDictionary.search("pad"); // return False
wordDictionary.search("bad"); // return True
wordDictionary.search(".ad"); // return True
wordDictionary.search("b.."); // return True

 

Constraints:

  • 1 <= word.length <= 25
  • word in addWord consists of lowercase English letters.
  • word in search consist of '.' or lowercase English letters.
  • There will be at most 3 dots in word for search queries.
  • At most 104 calls will be made to addWord and search.


class TrieNode:
    def __init__(self):
        self.children = {}
        self.eow = False

class WordDictionary:
    def __init__(self):
        self.root = TrieNode()
        
    def addWord(self, word: str) -> None:
        curr = self.root
        for c in word: 
            if c not in curr.children:
                curr.children[c] = TrieNode()
            curr = curr.children[c]
        curr.eow = True

    def search(self, word: str) -> bool:
        def dfs(k, root):
            curr = root
            for i in range(k, len(word)):
                c = word[i]
                if c == ".":
                    for child in curr.children.values():
                        if dfs(i+1, child):
                            return True
                    return False
                else:
                    if c not in curr.children:
                        return False
                    curr = curr.children[c]
            return curr.eow
        
        return dfs(0, self.root)
        


# Your WordDictionary object will be instantiated and called as such:
# obj = WordDictionary()
# obj.addWord(word)
# param_2 = obj.search(word)


Explained :









Labels:

Comments

Post a Comment

Popular posts from this blog

Leetcode 424. Longest Repeating Character Replacement. Python (Sliding Window)

  424 .  Longest Repeating Character Replacement You are given a string  s  and an integer  k . You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most  k  times. Return  the length of the longest substring containing the same letter you can get after performing the above operations .   Example 1: Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa. Example 2: Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.   Constraints: 1 <= s.length <= 10 5 s  consists of only uppercase English letters. 0 <= k <= s.length Solution :  class Solution: def characterReplacement(self, s: str, k: int) -> int: hm = {} ans = 0
Post a Comment
Read more

Leetcode 371. Sum of Two Integers. C++ / Java

371 .  Sum of Two Integers   Given two integers  a  and  b , return  the sum of the two integers without using the operators   +   and   - .   Example 1: Input: a = 1, b = 2 Output: 3 Example 2: Input: a = 2, b = 3 Output: 5   Constraints: -1000 <= a, b <= 1000 Solution :  C++ : class Solution { public: int getSum(int a, int b) { if (b==0) return a; int sum = a ^ b; int cr = (unsigned int) (a & b) << 1; return getSum(sum, cr); } }; Java :  class Solution { public int getSum(int a, int b) { while(b != 0){ int tmp = (a & b) << 1; a = a ^ b; b = tmp; } return a; } } Explaination :
Post a Comment
Read more

Leetcode 242. Valid Anagram. Python (3 Ways)

  242 .  Valid Anagram Given two strings  s  and  t , return  true   if   t   is an anagram of   s , and   false   otherwise . An  Anagram  is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.   Example 1: Input: s = "anagram", t = "nagaram" Output: true Example 2: Input: s = "rat", t = "car" Output: false   Constraints: 1 <= s.length, t.length <= 5 * 10 4 s  and  t  consist of lowercase English letters.   Follow up:  What if the inputs contain Unicode characters? How would you adapt your solution to such a case? class Solution: def isAnagram(self, s: str, t: str) -> bool: return sorted(s) == sorted(t) # return Counter(s) == Counter(t) # cs, ct = {}, {} # if len(s) != len(t): # return False # for i in range(len(s)): # cs[s[i]] = 1 + cs.get(s[i], 0) #
Post a Comment
Read more