package com.odyssey.app.algorithm.lc.trie;

/**
 * @author Dingsheng Huang
 * @date 2020/3/12 23:45
 *
 * 208
 * medium
 * https://leetcode.com/problems/implement-trie-prefix-tree/
 *
 * Implement a trie with insert, search, and startsWith methods.
 *
 * Example:
 *
 * Trie trie = new Trie();
 *
 * trie.insert("apple");
 * trie.search("apple");   // returns true
 * trie.search("app");     // returns false
 * trie.startsWith("app"); // returns true
 * trie.insert("app");
 * trie.search("app");     // returns true
 * Note:
 *
 * You may assume that all inputs are consist of lowercase letters a-z.
 * All inputs are guaranteed to be non-empty strings.
 *
 */
public class ImplementTrie {

    class Trie {
        String word = "";
        Trie[] children = new Trie[26];

        /** Initialize your data structure here. */
        public Trie() {

        }

        /** Inserts a word into the trie. */
        public void insert(String word) {
            Trie currNode = this;
            char[] chs = word.toCharArray();
            for (int i = 0; i < chs.length; i++) {
                int idx = chs[i] - 'a';
                if (currNode.children[idx] == null) {
                    currNode.children[idx] = new Trie();
                }
                currNode = currNode.children[idx];
            }
            currNode.word = word;
        }

        private boolean searchRes;
        /** Returns if the word is in the trie. */
        public boolean search(String word) {
            searchRes = false;
            dfs(this, word.toCharArray(), 0);
            return searchRes;
        }

        private boolean prefixRes;
        /** Returns if there is any word in the trie that starts with the given prefix. */
        public boolean startsWith(String prefix) {
            prefixRes = false;
            dfs2(this, prefix.toCharArray(), 0);
            return prefixRes;
        }

        private void dfs(Trie root, char[] chs, int idx) {
            if (root == null || idx == chs.length) {
                return;
            }
            if (root.children[chs[idx] - 'a'] != null) {
                // access the border
                if (idx == chs.length - 1) {
                    if (root.children[chs[idx] - 'a'].word.length() > 0) {
                        searchRes = true;
                    }
                }
                // next
                dfs(root.children[chs[idx] - 'a'], chs, idx + 1);
            }
        }

        private void dfs2(Trie root, char[] chs, int idx) {
            if (root == null || idx == chs.length) {
                return;
            }
            if (root.children[chs[idx] - 'a'] != null) {
                // access the border
                if (idx == chs.length - 1) {
                    prefixRes = true;
                }
                // next
                dfs(root.children[chs[idx] - 'a'], chs, idx + 1);
            }
        }

    }

    /**
     * Your Trie object will be instantiated and called as such:
     * Trie obj = new Trie();
     * obj.insert(word);
     * boolean param_2 = obj.search(word);
     * boolean param_3 = obj.startsWith(prefix);
     */
}