Trie

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

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

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

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

#### 例1）Trieの形
![제목 없는 다이어그램.drawio.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2961840/a83df9b6-d064-136c-95fe-e09adb37fa66.png)

#### 例2）ヤフーで東京を検索した時に表示される文字列
東京（Prefix）以降の人気ある文字列を取得し、画面で表示される
![스크린샷 2024-07-13 09.54.02.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2961840/aa406b8a-fa1c-2fc9-cf5e-4f1759763a29.png)


---
## Tireの長所と短所
### Tireの長所
- 文字列の検索が早い
  - Time complexity O(M)
### Tireの短所
- 文字列の長さ、すべのノードが必要なので、メモリの利用が多い


---

## Trieの実装例1

https://leetcode.com/problems/implement-trie-prefix-tree/description/

```java
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

```java
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を利用しなかった場合（全体探索する）
```java
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;
    }

```