Leetcode - search-suggestions-system

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

Given an array of strings products and a string searchWord. We want to design a system that suggests at most three product names from products after each character of searchWord is typed. Suggested products should have common prefix with the searchWord. If there are more than three products with a common prefix return the three lexicographically minimums products.

Return list of lists of the suggested products after each character of searchWord is typed.

Input: products = ["bags","baggage","banner","box","cloths"], searchWord = "bags"
Output: [["baggage","bags","banner"],["baggage","bags","banner"],["baggage","bags"],["bags"]]

The solution is using trie. Build a trie for products, store each product in the leaf. After that iterate searchWord and find the leaf node for each byte in searchWord. For this question, it only requires 3 results, just set limitation for the length of result.

func suggestedProducts(products []string, searchWord string) [][]string {
	root := buildTrie(products)

	node := root
	final := [][]string{}
	for i := 0; i < len(searchWord); i++ {
		index := searchWord[i] - 'a'
        result := []string{}
        if node != nil {
            node = node.children[index]
		    recursive(node, &result)
        }
        final = append(final, result)
	}

	return final
}

type TreeNode struct {
	value    string
	children []*TreeNode
}

func buildTrie(products []string) *TreeNode {
	root := &TreeNode{
		children: make([]*TreeNode, 26),
	}
	node := root
	for _, p := range products {
		node = root
		for _, b := range p {
			index := byte(b) - 'a'
			if node.children[index] != nil {
				node = node.children[index]
				continue
			}
			node.children[index] = &TreeNode{
				children: make([]*TreeNode, 26),
			}
			node = node.children[index]
		}
		node.value = p
	}

	return root
}

func recursive(root *TreeNode, result *[]string) {
	if len(*result) == 3 {
		return
	}
    if root == nil {
        return
    }

	if root.value != "" {
		*result = append(*result, root.value)
	}

	for i := 0; i < 26; i++ {
		if root.children[i] != nil {
			recursive(root.children[i], result)
		}
	}
}

func levelOrder(root *TreeNode) {
	queue := []*TreeNode{root}

	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			node := queue[i]
			for _, c := range node.children {
				if c != nil {
					queue = append(queue, c)
				}
			}
		}
		queue = queue[size:]
	}
}

# @param {String[]} products
# @param {String} search_word
# @return {String[][]}
def suggested_products(products, search_word)
    root = build_trie(products)
    node = root
    final = []
    for i in 0..search_word.length-1
        index = search_word[i].ord - 'a'.ord
        result = []
        if node != nil
            node = node.children[index]
            recursive(node, result)
        end
        final << result
    end
    
    return final
end

class TreeNode
     attr_accessor :val, :children
     def initialize(val)
         @val = val
         @children = Array.new(26)
     end
end

def build_trie(products)
    root = TreeNode.new("")
    node = root
    products.each do |product|
        node = root
        product.each_char do |p|
            index = p.ord - 'a'.ord
            if node.children[index].nil?
                node.children[index] = TreeNode.new("")
            end
            node = node.children[index]
        end
        node.val = product
    end
    return root
end

def recursive(root, result)
    if result.length == 3
        return
    end
    if root == nil 
        return
    end
    if root.val != ""
        result << root.val
    end
    for i in 0..25
        if root.children[i] != nil
            recursive(root.children[i], result)
        end     
    end
end

• 相关文章
• 全局相关文章