Implement a string matching algorithm that matches a given string prefix to the longest matching string in a dictionary.

Question

Utilisateur anonyme · Accepted Answer

Use a trie tree.

Ruby example:
class Trie
     def initialize()
       @trie = Hash.new()
     end
 
     def build(str) 
       node = @trie    
       str.each_char { |ch|
          cur = ch 
         prev_node = node
         node = node[cur]
         if node == nil 
           prev_node[cur] = Hash.new()
           node = prev_node[cur]
         end
      }
    end
 
    def find(str) 
      node = @trie
      str.each_char { |ch|
        cur = ch 
        node = node[cur]
        if node == nil 
          return false
        end
      }
      return true 
    end
 
  end

Amazon

Question d’entretien chez Amazon

Réponse à la question d'entretien

Entreprises suivies

Recherche d’emplois