This is the 23rd day of my participation in the August More Text Challenge.More challenges in August

Note: Part of the article content and pictures from the network, if there is infringement please contact me (homepage public number: small siege lion learning front)

By: Little front-end siege lion, home page: little front-end siege lion home page, source: Nuggets

GitHub: P-J27, CSDN: PJ wants to be a front-end siege lion

Copyright belongs to the author. Commercial reprint please contact the author for authorization, non-commercial reprint please indicate the source.

Add and search words (data structure design) – JavaScript (Regular +Trie+DFS)

Topic describes

Design a data structure that supports the following two operations:

void addWord(word)
bool search(word)
Copy the code

Search (word) searches for literal or regular expression strings that contain only letters. Or a – z. . Can represent any letter.

Example:

addWord("bad") addWord("dad") addWord("mad") search("pad") -> false search("bad") -> true search(".ad") -> true search("b.." ) -> trueCopy the code

You can assume that all words are made up of lowercase letters a-z.

Subject analysis

So the first instinct is to store all the words in an array. Each time a match is made, loop through the array to see if there are any strings that can be matched.

However, this method of violence has high time complexity and cannot be ac on the platform. So think of another way.

Solution 1: Clever regular expressions

There is a very clever way to use regular expressions: all words are no longer stored in an array, but are separated (word boundaries) by adding “#” before and after.

For example, bad and mad are added successively. So the internal string is: “#bad#mad#”. When we want to match the target string “.ad “, we just need to add “#” before and after the target string.

On leetcode, the js version in this case cannot be ac, but python3 does. It should be that the judgment conditions are relatively loose. The following code AC takes 2924ms.

from re import search
class WordDictionary:
    def __init__(self) :
        """ Initialize your data structure here. """
        self.words = The '#'
    def addWord(self, word: str) - >None:
        """ Adds a word into the data structure. """
        self.words += (word + The '#')
    def search(self, word: str) - >bool:
        """ Returns if the word is in the data structure. A word could contain the dot character '.' to represent any one letter. """
        return bool(search(The '#' + word + The '#', self.words))
        
Copy the code

Solution 2: Dictionary tree (Trie) + DFS

There is one data structure that is very efficient for recording/finding words: Trie. We can construct a dictionary tree that stores words into the dictionary tree each time addWord is called.

Note: when search is called, if the current character is not a., then the dictionary tree lookup logic is followed; Otherwise, because it is a wildcard, all characters in next of the current node are iterated, the same process as DFS.

The code is as follows:

var TrieNode = function() {
  this.next = {};
  this.isEnd = false;
};
​
var WordDictionary = function() {
  this.root = new TrieNode();
};
​
WordDictionary.prototype.addWord = function(word) {
  if(! word.length)return;
​
  let node = this.root;
  for (let i = 0; i < word.length; ++i) {
    if(! node.next[word[i]]) { node.next[word[i]] =new TrieNode();
    }
    node = node.next[word[i]];
  }
  node.isEnd = true;
};
​
​
WordDictionary.prototype.search = function(word) {
  if(! word.length)return false;
​
  return this.dfs(this.root, word);
};
​
​
WordDictionary.prototype.dfs = function(root, word) {
  const length = word.length;
  let node = root;
  for (let i = 0; i < length; ++i) {
    const ch = word[i];
    // If wildcard, try to traverse all cases (DFS)
    if (ch === ".") {
      const keys = Reflect.ownKeys(node.next);
      for (const key of keys) {
        const found = this.dfs(node.next[key], word.slice(i + 1));
        if (found) return true;
      }
      return false;
    }
​
    if(! node.next[ch]) {return false;
    }
    node = node.next[ch];
  }
  return node.isEnd;
};
Copy the code

Thank you for reading, I hope to help you, if there is a mistake or infringement of the article, you can leave a message in the comment area or add a public number in my home page to contact me.

Writing is not easy, if you feel good, you can “like” + “comment” thanks for your support ❤