import java.util.*;
/*
实现了一个简单版的，相对于normal trienode，加了一个set<string> strings. 表示有多少string的prefix是当前prefix
最关键的一点是：每insert一个word,就在经过的node加上这个word
还有就是全局变量prefix的使用
* */
public class AutocompleteSystem {
    class TrieNode{
        Map<Character, TrieNode> children = new HashMap<>();
        boolean isWordEnd = true;
        // strings with current prefix
        Set<String> strings = new HashSet<>();
    }
    private TrieNode root;
    public Map<String, Integer> map;
    String prefix;

    public AutocompleteSystem(String[] sentences, int[] times){
        root = new TrieNode();
        map = new HashMap<>();
        prefix = "";
        for(int i = 0; i < sentences.length; i++){
            map.put(sentences[i], times[i]);
            addSentence(sentences[i]);
        }

    }

    public void addSentence(String sentence){
        TrieNode cur = root;
        for(char c : sentence.toCharArray()){
            Map<Character, TrieNode> children = cur.children;
            if(!children.containsKey(c)){
                children.put(c, new TrieNode());
            }
            cur = children.get(c);
            System.out.println("current char:" + c);

            cur.strings.add(sentence);
            System.out.println(cur.strings);
        }
        cur.isWordEnd = true;
    }

    public List<String> input(char c){
        List<String> res = new ArrayList<>();
        if(c == '#'){
            addSentence(prefix);
            prefix = "";
            map.put(prefix, map.getOrDefault(prefix, 0) + 1);
            return res;
        }
        prefix += c;
        // search prefix
        TrieNode cur = root;
        for(char cc : prefix.toCharArray()){
            if(!cur.children.containsKey(cc)){
                return new ArrayList<>();
            }
            cur = cur.children.get(cc);
        }
        res.addAll(cur.strings);
        return res;
    }

    public static void main(String[] args){
        String[] sentences = {"i love you","ironman","island"};
        int[] times = {2,4,3};
        AutocompleteSystem obj = new AutocompleteSystem(sentences, times);
        System.out.println(obj.input('i'));
        System.out.println(obj.input(' '));
    }
}