SHARE
TWEET

Untitled

a guest Sep 18th, 2019 84 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public static int getMaxAutocomplete(ArrayList<String> titles, ArrayList<String> bodies, String prefix) {
  2.     Map<String,Integer> scores = new HashMap<String,Integer>();
  3.  
  4.     for (String title : titles) {
  5.         String [] words = title.split(" ");
  6.         for (int i = 0; i < words.length; i++) {
  7.             scores.put(words[i], scores.getOrDefault(words[i], 0) + 10);
  8.         }
  9.     }
  10.  
  11.     for (String body : bodies) {
  12.         String [] words = body.split(" ");
  13.         for (int i = 0; i < words.length; i++) {
  14.             scores.put(words[i], scores.getOrDefault(words[i], 0) + 1);
  15.         }
  16.     }
  17.  
  18.     int max = 0;
  19.     for(String word : scores.keySet()) {
  20.         if(word.length() >= prefix.length() && word.substring(0,prefix.length()).equals(prefix)) {
  21.             max = Math.max(max, scores.get(word));
  22.         }
  23.     }
  24.  
  25.     return max;
  26.  
  27. }
  28.  
  29. public class TrieNode {
  30.     int max;
  31.     TrieNode [] children = new int[26];
  32.     boolean endOfWord;
  33.  
  34.     public TrieNode(char c){
  35.         this.c = c;
  36.     }
  37. }
  38.  
  39. public class Trie {
  40.     private TrieNode root;
  41.  
  42.     public Trie() {
  43.         root = new TrieNode();
  44.     }
  45.  
  46.     // public void add(String word) {
  47.     //     TrieNode curr = root;
  48.     //     for (int i=0; i < word.length(); i++){
  49.     //         char c = word.charAt(i);
  50.     //         int index = c - 'A';
  51.  
  52.     //         if (curr.children[index] == null) {
  53.     //             TrieNode newNode = new TrieNode();
  54.     //             curr.children[index] = newNode;
  55.     //             curr = newNode;
  56.     //         } else {
  57.     //             curr = curr.children[index];
  58.     //         }
  59.     //     }
  60.     //     curr.endOfWord=true;
  61.     // }
  62.  
  63.     public int add(String word, int index, TrieNode curr) {
  64.         if (index == word.length() - 1) {
  65.             curr.max = scores
  66.             endOfWord = true;
  67.             return curr.max;
  68.         }
  69.  
  70.         char c = word.charAt(i);
  71.         int index = c - 'A';
  72.  
  73.         TrieNode newNode = new TrieNode();
  74.         if (curr.children[index] == null) {
  75.             curr.children[index] = newNode;
  76.         } else {
  77.             newNode = curr.children[index];
  78.         }
  79.  
  80.         curr.max = add(word, index + 1, newNode);
  81.  
  82.         return curr.max;
  83.  
  84.     }
  85.         // TrieNode curr = root;
  86.         // for (int i=0; i < word.length(); i++){
  87.         //     char c = word.charAt(i);
  88.         //     int index = c - 'A';
  89.  
  90.         //     if (curr.children[index] == null) {
  91.         //         TrieNode newNode = new TrieNode();
  92.         //         curr.children[index] = newNode;
  93.         //         curr = newNode;
  94.         //     } else {
  95.         //         curr = curr.children[index];
  96.         //     }
  97.         // }
  98.         // curr.endOfWord=true;
  99.     // }
  100.  
  101.     updateMaxes()
  102.  
  103.     public TrieNode searchNode(String prefix){
  104.         TrieNode curr = root;
  105.         for(int i = 0; i < s.length(); i++){
  106.             char c = s.charAt(i);
  107.             int index = c-'A';
  108.             if(curr.children[index] != null){
  109.                 curr = curr.children[index];
  110.             } else {
  111.                 return null;
  112.             }
  113.         }
  114.  
  115.         if (curr == root)
  116.             return null;
  117.  
  118.         return curr;
  119.     }
  120. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top