:orphan:

Design Add and Search Words
===========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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 ``2`` dots in ``word`` for ``search`` queries.
- At most ``10``\ :sup:```4``` calls will be made to ``addWord`` and
  ``search``.

.. highlight:: python

Pattern
-------
String, Depth-First Search, Design, Trie

Approaches
----------

.. tab-set::

    .. tab-item:: Trie With DFS

        **Code**

        .. literalinclude:: ../problems/medium/design-add-and-search-words-data-structure/design_add_and_search_words_data_structure__trie_with_dfs.py
            :language: python
            :lines: 16-

        **Test**

        >>> from design_add_and_search_words_data_structure__trie_with_dfs import WordDictionary
        >>> wd = WordDictionary()
        >>> wd.addWord("bad"); wd.addWord("dad"); wd.addWord("mad")
        >>> wd.search("pad")
        False
        >>> wd.search("bad")
        True
        >>> wd.search(".ad")
        True
        >>> wd.search("b..")
        True

        .. autoclass:: design_add_and_search_words_data_structure__trie_with_dfs.TrieNode
           :members:
           :show-inheritance:
           :undoc-members:

        .. autoclass:: design_add_and_search_words_data_structure__trie_with_dfs.WordDictionary
           :members:
           :show-inheritance:
           :undoc-members: