马小混

每日算法 - 实现 Trie (前缀树)

2019/05/05

每日算法 - 实现 Trie (前缀树)

一、题目描述

1 英文版

Implement a trie with insert, search, and startsWith methods.

Example:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");
trie.search("app");     // returns true

Note:

  • You may assume that all inputs are consist of lowercase letters a-z.
  • All inputs are guaranteed to be non-empty strings.

2 中文版

实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。

示例:

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // 返回 true
trie.search("app");     // 返回 false
trie.startsWith("app"); // 返回 true
trie.insert("app");
trie.search("app");     // 返回 true

说明:

  • 你可以假设所有的输入都是由小写字母 a-z 构成的。
  • 保证所有输入均为非空字符串。

二、ruby方案

1 什么是前缀树？

Trie树，即字典树，又称单词查找树或键树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计和排序大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：最大限度地减少无谓的字符串比较，查询效率比哈希表高。

Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。 它有3个基本性质：

  1. 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

trie

2 实现方案

如下，节点定义

TrieNode: full_word: false/true children: {}

full_word: 标识该节点是否是最后一个字符 children: 子节点使用hash，key是当前字符(‘a’-‘z’), value是子节点；

注意，TrieNode并没有val，因为val是a-z的一个分布，所以val就是{};

如图，hash的value是一个节点，节点的值又是一个hash

trie

1 insert

=begin
  前缀树单个节点定义
    fullword: 标识某一链路是否到达词尾，就是该字符是否是单词的词尾
    children: 该字符的子节点，'a'-'z', 为了节约空间，并不事先定义26的一个数组，而是一个hash，key是字符本身；
             ruby是动态数组，应该也能用，但是不太好查找比之hash 
=end
class TrieNode
  attr_accessor :fullword, :children

  def initialize
    @fullword = false
    @children = {}
  end
end

class Trie

=begin
    Initialize your data structure here.
=end
    def initialize
      @root = TrieNode.new
    end


=begin
    Inserts a word into the trie.
    :type word: String
    :rtype: Void
=end
    def insert(word)
      node = @root

      word.each_char do |char|
        # 如果没有创建一个节点，然后赋值给node
        node = (node.children[char] ||= TrieNode.new)
      end
      node.fullword = true
      nil
    end


=begin
    Returns if the word is in the trie.
    :type word: String
    :rtype: Boolean
=end
    def search(word)
      node = @root

      word.each_char do |char|
        return false unless node.children.key? char
        node = node.children[char]
      end

      node.fullword
    end


=begin
    Returns if there is any word in the trie that starts with the given prefix.
    :type prefix: String
    :rtype: Boolean
=end
    def starts_with(prefix)
      node = @root

      prefix.each_char do |char|
        return false unless node.children.key? char
        node = node.children[char]
      end

      true
    end


end

# Your Trie object will be instantiated and called as such:
# obj = Trie.new()
# obj.insert(word)
# param_2 = obj.search(word)
# param_3 = obj.starts_with(prefix)


Show Disqus Comments

Post Directory