Skip to content

Instantly share code, notes, and snippets.

@deepakkumarnd

deepakkumarnd/trie.rb

Last active September 22, 2022 13:59
Show Gist options
  • Save deepakkumarnd/823b8abf0d7785da47e0ec160757f8b1 to your computer and use it in GitHub Desktop.
Save deepakkumarnd/823b8abf0d7785da47e0ec160757f8b1 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. deepakkumarnd revised this gist Feb 21, 2021. 1 changed file with 3 additions and 2 deletions.
    5 changes: 3 additions & 2 deletions trie.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -11,13 +11,14 @@ def insert(new_word)

    if !contains?(word)
    temp = self

    prev = self
    word.each_char do |c|
    prev = temp
    i = to_index(c)
    temp = @hash[i] || (@hash[i] = Trie.new)
    end

    temp.value = word
    prev.value = word
    end
    end

  2. deepakkumarnd revised this gist Feb 20, 2021. 1 changed file with 20 additions and 10 deletions.
    30 changes: 20 additions & 10 deletions trie.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -1,39 +1,49 @@
    class Trie
    attr_accessor :hash, :word
    attr_accessor :hash, :value

    def initialize
    @hash = []
    @word = nil
    @hash = Array.new(26) { nil }
    @value = nil
    end

    def insert(new_word)
    if !contains?(new_word)
    word = new_word.downcase

    if !contains?(word)
    temp = self

    new_word.each_char do |c|
    temp = @hash[c.ord] || (@hash[c.ord] = Trie.new)
    word.each_char do |c|
    i = to_index(c)
    temp = @hash[i] || (@hash[i] = Trie.new)
    end

    temp.word = new_word
    temp.value = word
    end
    end

    def contains?(word)
    temp = self

    word.downcase!

    word.each_char do |c|
    if @hash[c.ord].nil?
    i = to_index(c)
    if @hash[i].nil?
    return false
    else
    temp = @hash[c.ord]
    temp = @hash[i]
    end
    end

    temp.has_word?
    end

    def has_word?
    !word.nil?
    !value.nil?
    end

    def to_index(c)
    c.ord - 'a'.ord
    end

    end
  3. deepakkumarnd created this gist Feb 20, 2021.
    53 changes: 53 additions & 0 deletions trie.rb
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,53 @@
    class Trie
    attr_accessor :hash, :word

    def initialize
    @hash = []
    @word = nil
    end

    def insert(new_word)
    if !contains?(new_word)
    temp = self

    new_word.each_char do |c|
    temp = @hash[c.ord] || (@hash[c.ord] = Trie.new)
    end

    temp.word = new_word
    end
    end

    def contains?(word)
    temp = self

    word.each_char do |c|
    if @hash[c.ord].nil?
    return false
    else
    temp = @hash[c.ord]
    end
    end

    temp.has_word?
    end

    def has_word?
    !word.nil?
    end

    end


    trie = Trie.new

    p trie.insert("parrot")
    p trie.insert("google")

    p trie.contains?("facebook")
    p trie.contains?("answer")
    p trie.contains?("googl")
    p trie.insert("monogram")
    p trie.contains?("parrot")