Python, without *26 factor in complexity


  • 15

    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))
    

  • 4
    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;
        }
    };
    

  • 0
    S

    @Longstation what is the reason for checking if (extensions.get(key) >= 2)?


  • 0
    D

    @sgupta33 I think I can answer this one, I ran into the same problem independently. It's because of the wording of the question, which says that search() looks for cases where exactly one change must occur.

    Suppose the dictionary contains just "apple" (and thus includes the wildcard version "appl*") and someone calls search("apple"). That needs to return false, because "apple" -> "apple" is zero transitions.

    However, the instant someone adds "apply" to the dictionary, then search("apple") should return true because there's a one-step path from "apple" to "apply". The same is true the other way around, because "apply"->"apple" is 1 step as well. Since each of those two dictionary words added "appl*", its weight should be 2.


  • 0

    Inspired by your answer, but probably already missed the point (brutal force and sadly have the *26 factor in hashing):

    class MagicDictionary(object):
        def buildDict(self, dict):
            self.d = {word[:i]+l+word[i+1:] for word in dict
                                            for i, w in enumerate(word)
                                            for l    in string.ascii_lowercase.replace(w, '')}
    
        def search(self, word):
            return word in self.d
    

Log in to reply
 

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