#9/20 Tries: Contacts [Cracking the Coding Interview Challenges]

#9 Tries: Contacts

www.hackerrank.com

シンプルなコンタクトリスト管理アプリケーションを作成する問題。

以下のフォーマットの入力が与えられる。

4
add hack
add hackerrank
find hac
find hak

1行目はオペレーション数、2行目以下は、スペース区切りでオペレーション(add or find)、オペレーションのパラメータ(文字列)となっている。 add の場合は、コンタクトリストへパラメータ(名前)を追加、findの場合はコンタクトリストからパラメータの文字列で始まるコンタクトの総数を表示する。

上記の入力の場合、実行結果は以下となる。

2
0

solution

以下はrubyでの解。問題タイトルにあるように、トライ木のアルゴリズムを使って解いている。

#!/bin/ruby

class Node
    CHARACTER_OF_NODE = 26
    
    def initialize()
        @children = Array.new(CHARACTER_OF_NODE)
        @size = 0
    end

    def add(str, index = 0)
        @size += 1
        return if str.size == index
        
        current = str[index]
        child = getNode(current)
        if child == nil
            child = Node.new
            setNode(current, child)
        end
        child.add(str, index + 1)
    end
    
    def findContact(str, index = 0)
        return @size if str.size == index
        child = getNode(str[index])
        return 0 if child == nil
        return child.findContact(str, index + 1)
    end
    
    private 
        def getCharIndex(c)
            return c.ord - 'a'.ord
        end

        def getNode(c)
            return @children[getCharIndex(c)]
        end

        def setNode(c, node)
            @children[getCharIndex(c)] = node
        end
end

input = $stdin.read.split("\n")
n, contacts, list, node = input.shift, input, [], Node.new
contacts.each do |v|
    operation, name = v.split(" ")
    
    case operation
        when "add" then node.add(name)
        when "find" then puts node.findContact(name)
    end
end

github.com

トライ木とは

トライ木（英: trie）やプレフィックス木（英: prefix tree）とは、順序付き木の一種。あるノードの配下の全ノードは、自身に対応する文字列に共通するプレフィックス（接頭部）があり、ルート（根）には空の文字列が対応している。値は一般に全ノードに対応して存在するわけではなく、末端ノードや一部の中間ノードだけがキーに対応した値を格納している。2分探索木と異なり、各ノードに個々のキーが格納されるのではなく、木構造上のノードの位置とキーが対応している。

トライ木 - Wikipedia

まとめ

ゴリ推しで解こうとしても、大抵の場合はテストケースがタイムアウトし、パスできないようになっている。

トライ木を使えば高速にキー検索を行えるため、全てのテストケースをパスできた。

実際にトライ木アルゴリズムを書いたのは初めてかもしれない。とても美しい。