1268. Search Suggestions System

https://leetcode.com/problems/search-suggestions-system/

Python

Tire Tree with member of matched words

class Solution:
    MATCHED_KEY = '#'
    def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
        products.sort()

        # Build the trie tree, and remember the matched products under a special key: MATCHED_KEY
        trie = {}
        cur = trie
        for product in products:
            cur = trie
            for letter in product:
                cur = cur.setdefault(letter, {})
                matched = cur.setdefault(self.MATCHED_KEY, [])
                if len(matched) < 3:
                    matched.append(product)


        # Travel the characters in searchWord, and get the result from the memory
        result = []
        cur = trie

        is_matched = True  # Default from empty string, which "is_matched" true
        for i, char in enumerate(searchWord):
            if char not in cur:
                is_matched = False

            if not is_matched:
                result.append([])
                continue

            cur = cur[char]
            result.append(cur[self.MATCHED_KEY])

        return result

Javascript

var suggestedProducts = function (products, searchWord) {
	const trie = new Trie();
	trie.insert(products);
	return trie.find(searchWord);
};

class Trie {
	constructor() {
		this.root = { childs: {} };
		this.max = 3;
	}

	insert(products) {
    for (let product of products) {
      let node = this.root;
      for (let char of product) {
				if (!node.childs[char]) node.childs[char] = { childs: {} };
        node = node.childs[char];
      }
      node.isMatched = product;
    }
	}

	find(searchWord) {
    let node = this.root;
    const res = [];
    for (const char of searchWord) {
      if (node) {
        res.push(this.deeper(node.childs[char]))
        node = node.childs[char];
      } else {
        res.push([])
      }
    }
    return res;
	}

  deeper(node, result = []) {
    if (result.length === this.max || !node) return result;
    if (node.isMatched) {
      result.push(node.isMatched)
    }

		for (let i = "a".charCodeAt(0); i <= "z".charCodeAt(0); i++) {
			const char = String.fromCharCode(i);
			if (node.childs[char]) {
				this.deeper(node.childs[char], result);
			}
		}
    return result;
  }
}