Trie

概要

コーディング試験でよくみられる
Prefixあるか、文字列検索せよ
みたいなのは

完全検索でできるが、
面接に行ったら、「もっと改善できるか」と聞かれる

「私の考えはTrie（トライ木）を利用します」と話せば、半分は合うかと思う

Trieとは

1. 文字列を保存し、効率的に探索するためのTree形式のデータ構成
2. 自動完成機能、辞書検索などの文字列を探索するために特化されている
3. 例えば、Appleの検索するためには、一番最初にAを探し、その後p、pの順番で探せばいい。こういう画面を適応したものがTrie（トライ木）

例1）Trieの形

例2）ヤフーで東京を検索した時に表示される文字列

東京（Prefix）以降の人気ある文字列を取得し、画面で表示される

---

Tireの長所と短所

Tireの長所

• 文字列の検索が早い
  • Time complexity O(M)

Tireの短所

• 文字列の長さ、すべのノードが必要なので、メモリの利用が多い

---

Trieの実装例1

package com.leetcode.midium;

import java.util.HashMap;

public class ImnplementTrie208 {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("abc");
        boolean result = trie.startsWith("ab");
        System.out.println(result);
    }


    static class TrieNode {
        HashMap<Character, TrieNode> trieNode;
        boolean isEndOfWord;

        TrieNode() {
            this.trieNode = new HashMap<>();
            this.isEndOfWord = false;
        }
    }

    static class Trie {
        private final TrieNode root;

        public Trie() {
            root = new TrieNode();
        }

        public void insert(String word) {
            // Objectが作成された時点のRootを持ってくる
            TrieNode current = root;

            for (char w : word.toCharArray()) {
                // wが存在しなかったら、wをTreeの最後に追加する
                // 最後のは常に最後になる
                current = current.trieNode.computeIfAbsent(w, ww -> new TrieNode());
            }
            current.isEndOfWord = true;
        }

        public boolean startsWith(String prefix) {
            TrieNode current = root;
            for (char p : prefix.toCharArray()) {
                current = current.trieNode.get(p);
                if (current == null) {
                    return false;
                }
            }
            return true;
        }


        public boolean search(String word) {
            TrieNode current = root;

            for (char w : word.toCharArray()) {
                current = current.trieNode.get(w);
                if (current == null) {
                    return false;
                }
            }
            return current.isEndOfWord;
        }
    }
}

Trieの実装例2

長いPrefixを求めよ

例）
"flower", "flow", "flight"
->
fl

"flow", "flower", "flowchart"
->
flow

package com.leetcode.midium;

import java.util.*;

public class Main {
    static class TrieNode {

        private String result;
        private HashMap<Character, TrieNode> trieNode;
        private boolean isEndOfWord;

        TrieNode() {
            this.trieNode = new HashMap<>();
            this.isEndOfWord = false;
            this.result = "";
        }

        public String getResult() {
            return result;
        }
    }

    static class Trie {
        private final TrieNode root;

        public Trie() {
            root = new TrieNode();
        }


        public void insert(String word) {
            TrieNode current = root;
            for (char w : word.toCharArray()) {
                current = current.trieNode.computeIfAbsent(w, ww -> new TrieNode());
            }
            current.isEndOfWord = true;
            root.result = word;
        }


        public boolean startWith(String prefix) {
            TrieNode current = root;
            String temp = "";
            for (char p : prefix.toCharArray()) {
                current = current.trieNode.get(p);
                if (current == null) {
                    root.result = temp;
                    return false;
                }
                temp += p;
            }
            root.result = temp;
            return true;
        }
    }


    public static String commonPrefix(List<String> words) {

        if (words == null || words.isEmpty()) {
            return "";
        }
        
        Trie trie = new Trie();

        trie.insert(words.get(0));

        for (int i = 1; i < words.size(); i++) {
            trie.startWith(words.get(i));
        }
        return trie.root.getResult();
    }


    public static void main(String[] args) {
        System.out.println(commonPrefix(Arrays.asList("flower", "flow", "flight")));   // -> "fl"
        System.out.println(commonPrefix(Arrays.asList("flow", "flower", "flowchart")));   // -> "flow"
        System.out.println(commonPrefix(Arrays.asList("flower", "flow", "flowchart")));   // -> "flow"
        System.out.println(commonPrefix(Arrays.asList("car", "cat", "dog", "bird", "cow", "rabbit")));   // -> ""
        System.out.println(commonPrefix(Arrays.asList("one word")));   // -> "one word"
        System.out.println(commonPrefix(Arrays.asList("")));   // -> ""
        System.out.println(commonPrefix(Arrays.asList()));   // -> ""
    }
}

実行結果

Connected to the target VM, address: '127.0.0.1:50206', transport: 'socket'
fl
flow
flow

one word


Disconnected from the target VM, address: '127.0.0.1:50206', transport: 'socket'

Trieを利用しなかった場合（全体探索する）

public static String commonPrefix(List<String> strs) {
        if (strs == null || strs.isEmpty()) {
            return "";
        }
        if (strs.size() == 1) {
            return strs.get(0);
        }

       
        String prefix = strs.get(0);
        for (int i = 1; i < strs.size(); i++) {
            while (strs.get(i).indexOf(prefix) != 0) {
              
                prefix = prefix.substring(0, prefix.length() - 1);
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }
        return prefix;
    }