211 Design Add and Search Words Data Structure¶

:::tip Hint

Use recursive trie traverse :::

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

C# Solution¶

using System.Linq;
using System.Collections.Generic;
using System;

namespace Algorithms.Medium
{
  public class WordDictionary : Trie
  {

    public override bool Search(string v, bool isStartsWith = false)
    {
      return SearchRange(v, 0, root.children);
    }

    private bool SearchRange(string word, int start, Dictionary<char, TrieNode> children)
    {

      if (start >= word.Length)
      {
        return false;
      }

      if (children.ContainsKey(word[start]))
      {
        if (start == word.Length - 1)
        {
          return children[word[start]].endOfWord;
        }
        return SearchRange(word, start + 1, children[word[start]].children);
      }
      else
      {
        if (word[start] == '.')
        {
          foreach (var key in children.Keys)
          {
            if (start == word.Length - 1 && children.ContainsKey(key) && children[key].endOfWord)
            {
              return true;
            }
            if (SearchRange(word, start + 1, children[key].children))
            {
              return true;
            }
          }
          return false;
        }
        else
        {
          return false;
        }
      }
    }
  }
}

C# Tests¶

using Algorithms.Medium;
using Xunit;

namespace AlgorithmTests.Medium
{
  public class WordDictionaryTests
  {
    [Fact]
    public void TestName()
    {
      var wordDictionary = new WordDictionary();
      wordDictionary.Insert("bad");
      wordDictionary.Insert("dad");
      wordDictionary.Insert("mad");

      Assert.False(wordDictionary.Search("pad"));
      Assert.True(wordDictionary.Search("bad"));
      Assert.True(wordDictionary.Search(".ad"));
      Assert.True(wordDictionary.Search("b.."));
    }
  }
}