class TrieNode {
    // Initialize your data structure here.
    char val;
    HashMap<Character, TrieNode> children = new HashMap<>();
    boolean hasWord;

    public TrieNode() {}

    public TrieNode(char val) {
        this.val = val;
    }
}

public class Trie {
    private TrieNode root;

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

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode currNode = root;
        HashMap<Character, TrieNode> children = root.children;
        char[] wordArray = word.toCharArray();

        for (int i = 0; i < wordArray.length; i++) {
            currNode = children.get(wordArray[i]);
            if (currNode == null) {
                currNode = new TrieNode(wordArray[i]);
                children.put(wordArray[i], currNode);
            }
            children = currNode.children;
        }
        currNode.hasWord = true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode rst = searchWordNodePos(word);
        if (rst == null) return false;
        return rst.hasWord;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode rst = searchWordNodePos(prefix);
        return rst != null;
    }

    public TrieNode searchWordNodePos(String word) {
        TrieNode currNode = root;
        HashMap<Character, TrieNode> children = root.children;
        char[] wordArray = word.toCharArray();

        for (int i = 0; i < wordArray.length; i++) {
            currNode = children.get(wordArray[i]);
            if (currNode == null) return null;
            children = currNode.children;
        }

        return currNode;
    }
}

    private static Map<String, Boolean> initPrefixTree(String[] words) {
        Map<String, Boolean> hash = new TreeMap<>();
        for (String word : words) {
            hash.putIfAbsent("", false);

            StringBuilder sb = new StringBuilder();
            for (char c : word.toCharArray()) {
                sb.append(c);
                hash.putIfAbsent(sb.toString(), false); // 要用 putIfAbsent. 避免覆盖true的情况
            }
            hash.put(sb.toString(), true);  // 要用 put. 有true一定要为true  e.g. "ab" "abb"
        }
        return hash;
    }

add and search word

word search ii

word square