Guest User

Untitled

a guest
Sep 18th, 2019
87
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