TLE Disaster | both hashmap and Trie giving TLE
HashMap\n\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        \n        \n\n        int n=words.length;\n        int ans[]=new int[n]
1. HashMap\n```\nclass Solution {\n    public int[] sumPrefixScores(String[] words) {\n        \n        \n\n        int n=words.length;\n        int ans[]=new int[n];\n        \n        HashMap<String,Integer> map=new HashMap<>();\n        HashMap<Integer,HashSet<String>> sub_str=new HashMap<>();\n        for(int i=0; i<n; i++){\n            StringBuilder sb=new StringBuilder();\n            for(int j=0; j<words[i].length(); j++){\n                sb.append(words[i].charAt(j));\n                if(!sub_str.containsKey(i))\n                    sub_str.put(i,new HashSet<>());\n                sub_str.get(i).add(sb.toString());\n                map.put(sb.toString(),map.getOrDefault(sb.toString(),0)+1);\n            }\n        }\n        for(int i=0; i<n; i++){\n            int count=0;\n            for(String str:sub_str.get(i)){\n                Integer get=map.get(str);\n                if(get==null) break;\n                count+=get;\n            }\n            ans[i]=count;\n        }\n        \n        return ans;\n    }\n}\n```\n2. Trie\n```\nclass Solution {\n    class Node{\n    Node links[];\n    boolean flag;\n    int count;\n    public Node(){\n        links=new Node[26];\n        flag=false;\n        count=0;\n    }\n    boolean containsKey(char c){\n        return links[c-\'a\']!=null;\n    }\n    Node get(char c){\n        return links[c-\'a\'];\n    }\n    void put(char c,Node toadd){\n        links[c-\'a\']=toadd;\n    }\n    void setEnd(){\n        flag=true;\n    }\n    boolean isEnd(){\n        return flag;\n    }\n       \n}\nclass Trie {\n    Node root;\n    public Trie() {\n        root=new Node();\n    }\n    \n    public void insert(String word) {\n        Node node=root;\n        for(char c:word.toCharArray()){\n            if(!node.containsKey(c)){\n                node.put(c,new Node());\n            }\n            node=node.get(c); \n            node.count++;\n        }\n        node.setEnd();\n        \n    }\n    \n    public boolean search(String word) {\n        Node node=root;\n        for(char c:word.toCharArray()){\n            if(!node.containsKey(c)) return false;\n            \n            node=node.get(c);\n        }\n        return node.isEnd();\n    }\n    \n    public int startsWith(String prefix) {\n        Node node=root;\n        for(char c:prefix.toCharArray()){\n            if(!node.containsKey(c)) return 0;\n            node=node.get(c);\n        }\n        return node.count;\n    }\n}\n    public int[] sumPrefixScores(String[] words) {\n        \n        \n        Trie root=new Trie();\n        int n=words.length;\n        int ans[]=new int[n];\n        \n        for(int i=0; i<n; i++){\n            root.insert(words[i]);\n        }\n        \n        for(int i=0; i<n; i++){\n            StringBuilder sb=new StringBuilder();\n            int count=0;\n            for(int j=0; j<words[i].length(); j++){\n                sb.append(words[i].charAt(j));\n                count+=root.startsWith(sb.toString());\n            }\n            ans[i]=count;\n        }\n        \n        return ans;\n    }\n}\n```\n\n3. Trie Accepted\n```\nclass Solution {\n    class Node{\n    Node links[];\n    boolean flag;\n    int count;\n    public Node(){\n        links=new Node[26];\n        flag=false;\n        count=0;\n    }\n    boolean containsKey(char c){\n        return links[c-\'a\']!=null;\n    }\n    Node get(char c){\n        return links[c-\'a\'];\n    }\n    void put(char c,Node toadd){\n        links[c-\'a\']=toadd;\n    }\n    void setEnd(){\n        flag=true;\n    }\n    boolean isEnd(){\n        return flag;\n    }\n       \n}\nclass Trie {\n    Node root;\n    public Trie() {\n        root=new Node();\n    }\n    \n    public void insert(String word) {\n        Node node=root;\n        for(char c:word.toCharArray()){\n            if(!node.containsKey(c)){\n                node.put(c,new Node());\n            }\n            node=node.get(c); \n            node.count++;\n        }\n        node.setEnd();\n        \n    }\n    \n    public boolean search(String word) {\n        Node node=root;\n        for(char c:word.toCharArray()){\n            if(!node.containsKey(c)) return false;\n            \n            node=node.get(c);\n        }\n        return node.isEnd();\n    }\n    \n    public int startsWith(String prefix) {\n\n        Node node=root;\n        int ans=node.count;\n        for(char c:prefix.toCharArray()){\n            node=node.get(c);\n            ans+=node.count;\n        }\n        return ans;\n    }\n}\n    public int[] sumPrefixScores(String[] words) {\n        Trie root=new Trie();\n        int n=words.length;\n        int ans[]=new int[n];\n        \n        for(int i=0; i<n; i++){\n            root.insert(words[i]);\n        }\n        \n        for(int i=0; i<n; i++){\n            \n            ans[i]=root.startsWith(words[i]);\n        }\n        \n        return ans;\n    }\n}\n```
['Trie']