Untitled
plain_text
a month ago
2.8 kB
1
Indexable
Never
package Autocomplete; import java.util.ArrayList; import java.util.HashMap; class UserSolution { private static final int ALPHABET_SIZE = 26; private final HashMap<String, Word> mapWord = new HashMap<>(); private Trie root; private int order; void init() { mapWord.clear(); root = new Trie(); order = 0; } void inputWord(char[] mWord) { order++; String str = new String(mWord).trim(); Word word = mapWord.get(str); if (word == null) { word = new Word(str, order); mapWord.put(str, word); Trie temp = root; for (char c : str.toCharArray()) { int index = c - 'a'; if (temp.node[index] == null) { temp.node[index] = new Trie(); } temp = temp.node[index]; temp.list.add(word); } } else { if (word.count == 0) return; word.count++; word.order = order; } } int recommend(char[] mUser, char[] mAnswer) { String str = new String(mUser).trim(); Trie temp = root; for (char c : str.toCharArray()) { int index = c - 'a'; if (temp.node[index] == null) { output(str, mAnswer); return str.length(); } temp = temp.node[index]; } String res = temp.findWord(str); output(res, mAnswer); return res.length(); } void output(String str, char[] mAnswer) { System.arraycopy(str.toCharArray(), 0, mAnswer, 0, str.length()); mAnswer[str.length()] = '\0'; } void banWord(char[] mWord) { String str = new String(mWord).trim(); Word word = mapWord.get(str); if (word != null) { word.count = 0; } else { word = new Word(str, order); word.count = 0; mapWord.put(str, word); } } static class Word { final String str; int count; int order; public Word(String str, int order) { this.str = str; this.count = 1; this.order = order; } } static class Trie { final ArrayList<Word> list = new ArrayList<>(); final Trie[] node = new Trie[ALPHABET_SIZE]; String findWord(String str) { Word res = new Word(str, Integer.MAX_VALUE); res.count = 0; for (Word word : list) { if (word.count > res.count || (word.count == res.count && word.order > res.order)) { res = word; } } return res.str; } } }