Magic Dictionary

New problem by LeetCode: https://leetcode.com/problems/implement-magic-dictionary/description/

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:

1. You may assume that all the inputs are consist of lowercase letters a-z.
2. For contest purpose, the test data is rather small by now. You could think about highly efficient algorithm after the contest.
3. 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.

Many ways to solve this problem, but I chose to optimize to make the search operation faster rather than the build dictionary.
Approach: when you're building the dictionary, for each input word W, add to the dictionary (in a hash table) all the potential permutations of W using a wildcard, which we can represent by '*'. Easier to show an example: suppose the word to be added is "trump" (what..). Then what you'll really add to the dictionary is the following list: "*rump", "t*ump", "tr*mp", "tru*p" and "trum*". There is one more thing: when you add the variations to the hash table, the key will be the variation itself, but as the value do one thing: keep another hash table with the characters that have been replaced by the wildcard. For instance, when you add "t*ump", here is the key and the value:

Key: t*ump
Value: r (inside another hash table)

The value will be important during the search operation (more on this shortly). OK, to build the dictionary then the complexity will be O(number of words * number of characters in the longest word).

For the search, do a similar computation by changing the given word to be searched S with the wildcards and checking whether any variation is in the dictionary hash table. If so, then you have one more check to do: check whether the character that got replaced in S is in the value of the matched entry in the dictionary. If it isn't, we're good, we found a match with one char off. But if it is, make sure that there is at least one more character there. Otherwise what's happening is that S matches exactly one of the initial input words, which is undesirable - there must be at least one character off. Kind of confusing, but it is what it is. (Time) Complexity for the search operation: O(number of characters in the input word being searched). Code is below, cheers, Marcelo.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Numerics;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace LeetCode
{
    class Program
    {
        static void Main(string[] args)
        {
            MagicDictionary obj = new MagicDictionary();
            obj.BuildDict(new string[] { "hello", "leetcode" });
            Console.WriteLine(obj.Search(args[0]));
        }
    }

    public class MagicDictionary
    {
        private Hashtable allWords;
        /** Initialize your data structure here. */
        public MagicDictionary()
        {
            allWords = new Hashtable();
        }

        /** Build a dictionary through a list of words */
        public void BuildDict(string[] dict)
        {
            foreach (string s in dict)
            {
                StringBuilder sb = new StringBuilder(s);
                for (int i = 0; i < s.Length; i++)
                {
                    char c = s[i];
                    sb = new StringBuilder(s);
                    sb[i] = '*';
                    if (!allWords.ContainsKey(sb.ToString()))
                    {
                        Hashtable charSet = new Hashtable();
                        charSet.Add(c, true);
                        allWords.Add(sb.ToString(), charSet);
                    }
                    else
                    {
                        Hashtable charSet = (Hashtable)allWords[sb.ToString()];
                        if (!charSet.ContainsKey(c))
                        {
                            charSet.Add(c, true);
                            allWords[sb.ToString()] = charSet;
                        }
                    }
                }
            }
        }

        /** Returns if there is any word in the trie that equals to the given word after modifying exactly one character */
        public bool Search(string word)
        {
            for (int i = 0; i < word.Length; i++)
            {
                StringBuilder sb = new StringBuilder(word);
                char c = word[i];
                sb[i] = '*';
                if (allWords.ContainsKey(sb.ToString()))
                {
                    Hashtable charSet = (Hashtable)allWords[sb.ToString()];
                    if (charSet.Count > 1 || !charSet.ContainsKey(c))
                    {
                        return true;
                    }
                }
            }

            return false;
        }
    }

    /**
     * Your MagicDictionary object will be instantiated and called as such:
     * MagicDictionary obj = new MagicDictionary();
     * obj.BuildDict(dict);
     * bool param_2 = obj.Search(word);
     */
}