Python, without *26 factor in complexity
A word 'apple' has neighbors '*pple', 'a*ple', 'ap*le', 'app*e', 'appl*'.  When searching for a target word like 'apply', we know that a necessary condition is 
A word `'apple'` has neighbors `'*pple', 'a*ple', 'ap*le', 'app*e', 'appl*'`.  When searching for a target word like `'apply'`, we know that a necessary condition is a neighbor of `'apply'` is a neighbor of some source word in our magic dictionary.  If there is more than one source word that does this, then at least one of those source words will be different from the target word.  Otherwise, we need to check that the source doesn't equal the target.\n\n```python\nclass MagicDictionary(object):\n    def _candidates(self, word):\n        for i in xrange(len(word)):\n            yield word[:i] + '*' + word[i+1:]\n            \n    def buildDict(self, words):\n        self.words = set(words)\n        self.near = collections.Counter(cand for word in words\n                                        for cand in self._candidates(word))\n\n    def search(self, word):\n        return any(self.near[cand] > 1 or \n                   self.near[cand] == 1 and word not in self.words\n                   for cand in self._candidates(word))\n```
[]