Wildcard search

Questions 1 to 5 of 7

1. 1. In the wildcard search lesson, what does a dot . in a search pattern match?

   Any one letter, so the search tries every child at that levelExactly the next letter stored under the same parentZero or more letters, the way * works in many file searchesOnly letters that the pattern has not used yet
2. 2. The dictionary holds bad, dad and mad. search for .ad returns True. Why does it never try the d or m child at the root?

   The pattern is three characters, so the root has no more children to checkThe b branch matches bad first, and search returns True at the first branch that succeedsA dot at the start of a pattern is only compared with the last child added to the rootThe end flag on the root is True, so the answer is known before any branch is tried
3. 3. What does this program print? ``python class Node: def __init__(self): self.children = [None] * 26 self.is_end = False class WordDictionary: def __init__(self): self.root = Node() def add_word(self, word): node = self.root for ch in word: i = ord(ch) - ord("a") if node.children[i] is None: node.children[i] = Node() node = node.children[i] node.is_end = True def search(self, pattern): return self._search(self.root, pattern, 0) def _search(self, node, pattern, i): if i == len(pattern): return node.is_end ch = pattern[i] if ch == ".": return any( self._search(child, pattern, i + 1) for child in node.children if child is not None ) child = node.children[ord(ch) - ord("a")] return child is not None and self._search(child, pattern, i + 1) def find_all(self, pattern): found = [] self._collect(self.root, pattern, 0, [], found) return found def _collect(self, node, pattern, i, path, found): if i == len(pattern): if node.is_end: found.append("".join(path)) return ch = pattern[i] if ch == ".": for k, child in enumerate(node.children): if child is not None: path.append(chr(ord("a") + k)) self._collect(child, pattern, i + 1, path, found) path.pop() else: child = node.children[ord(ch) - ord("a")] if child is not None: path.append(ch) self._collect(child, pattern, i + 1, path, found) path.pop() d = WordDictionary() for w in ["cot", "cut", "cat", "dog", "cart"]: d.add_word(w) print(d.find_all("c.t"), d.find_all(".o.")) ``

   ['cat', 'cot', 'cut'] ['dog', 'cot']['cot', 'cut', 'cat'] ['cot', 'dog']['cat', 'cot', 'cut', 'cart'] ['cot', 'dog']['cat', 'cot', 'cut'] ['cot', 'dog']
4. 4. What does this program print? ``python class Node: def __init__(self): self.children = [None] * 26 self.is_end = False class WordDictionary: def __init__(self): self.root = Node() def add_word(self, word): node = self.root for ch in word: i = ord(ch) - ord("a") if node.children[i] is None: node.children[i] = Node() node = node.children[i] node.is_end = True def search(self, pattern): return self._search(self.root, pattern, 0) def _search(self, node, pattern, i): if i == len(pattern): return node.is_end ch = pattern[i] if ch == ".": return any( self._search(child, pattern, i + 1) for child in node.children if child is not None ) child = node.children[ord(ch) - ord("a")] return child is not None and self._search(child, pattern, i + 1) def find_all(self, pattern): found = [] self._collect(self.root, pattern, 0, [], found) return found def _collect(self, node, pattern, i, path, found): if i == len(pattern): if node.is_end: found.append("".join(path)) return ch = pattern[i] if ch == ".": for k, child in enumerate(node.children): if child is not None: path.append(chr(ord("a") + k)) self._collect(child, pattern, i + 1, path, found) path.pop() else: child = node.children[ord(ch) - ord("a")] if child is not None: path.append(ch) self._collect(child, pattern, i + 1, path, found) path.pop() d = WordDictionary() for w in ["cat", "cart"]: d.add_word(w) print(" ".join(f"{p}={d.search(p)}" for p in ["c...", "..r", "c..", "...."])) ``

   c...=False ..r=True c..=False ....=Falsec...=True ..r=False c..=True ....=Truec...=True ..r=True c..=False ....=Falsec...=True ..r=False c..=True ....=False
5. 5. The search below crashes on the pattern b.. Which line causes the crash? ``python def search(node, pattern, i): if i == len(pattern): return node.is_end ch = pattern[i] child = node.children[ord(ch) - ord("a")] return child is not None and search(child, pattern, i + 1) ``

   return node.is_end, because the end flag is read before the pattern is used upif i == len(pattern):, because it compares a count with a characterchild = node.children[ord(ch) - ord("a")], because the dot gives an index of -51, outside the 26-slot listreturn child is not None and search(child, pattern, i + 1), because a None child is never safe to test