Python, without *26 factor in complexity


  • 7

    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.

    class MagicDictionary(object):
        def _candidates(self, word):
            for i in xrange(len(word)):
                yield word[:i] + '*' + word[i+1:]
                
        def buildDict(self, words):
            self.words = set(words)
            self.near = collections.Counter(cand for word in words
                                            for cand in self._candidates(word))
    
        def search(self, word):
            return any(self.near[cand] > 1 or 
                       self.near[cand] == 1 and word not in self.words
                       for cand in self._candidates(word))
    

  • 1
    L

    Inspired by your idea, here is the Java version. (beats 90.75 %)

    public class MagicDictionary {
      Set<String> originalWords;
      Map<String, Integer> extensions;
    
      /**
       * Initialize your data structure here.
       */
      public MagicDictionary() {
        originalWords = new HashSet<>();
        extensions = new HashMap<>();
      }
    
      /**
       * Build a dictionary through a list of words
       */
      public void buildDict(String[] dict) {
        char[] str;
        int n;
        char temp;
        for (String word : dict) {
          originalWords.add(word);
          str = word.toCharArray();
          n = word.length();
          for (int i = 0; i < n; i++) {
            temp = str[i];
            str[i] = '*';
            String key = new String(str);
            extensions.put(key, extensions.getOrDefault(key, 0) + 1);
            str[i] = temp;
          }
        }
      }
    
      /**
       * Returns if there is any word in the trie that equals to the given word after modifying exactly one character
       */
      public boolean search(String word) {
        int n = word.length();
        char[] str = word.toCharArray();
        char temp;
        String key;
        for (int i = 0; i < n; i++) {
          temp = str[i];
          str[i] = '*';
          key = new String(str);
          if (extensions.containsKey(key)) {
            if (extensions.get(key) >= 2) {
              return true;
            }
            if (!originalWords.contains(word)) {
              return true;
            }
          }
          str[i] = temp;
        }
        return false;
      }
    }
    
    

  • 0

    My solution is similar:

    class MagicDictionary {
    public:
        unordered_map<string, char> map;
    
        void buildDict(vector<string> dict) {
            for (string &word : dict) {
                for (int i = 0; i < word.size(); i++) {
                    string mw = word;
                    mw[i] = '0';
                    if (!map.count(mw))
                        map[mw] = word[i];
                    else if (map[mw] != word[i])
                        map[mw] = 0;
                }
            }
        }
        
        bool search(string word) {
            for (int i = 0; i < word.size(); i++) {
                string mw = word;
                mw[i] = '0';
                if (map.count(mw) && map[mw] != word[i])
                    return true;
            }
            return false;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.