/** * This problem was asked by Twitter. Implement an autocomplete system. That is, given a query string s and a set of all possible query strings, return all strings in the set that have s as a prefix. For example, given the query string de and the set of strings [dog, deer, deal], return [deer, deal]. Hint: Try preprocessing the dictionary into a more efficient data structure to speed up queries. * */ class Problem_949 { /* * solution: DFS and Trie Tree(prefix tree), add all word into prefix tree for searching; * Time and Space complexity are: O(2^L), L is the length of key word * */ private var root: TrieNode? = null init { root = TrieNode() } fun getSamePrefix(query: String, strings: ArrayList<String>): ArrayList<String> { val result = ArrayList<String>() for (word in strings) { root?.insert(word) } var lastNode = root val sb = StringBuilder() //find out the last node for start dfs for (c in query) { lastNode = lastNode?.children?.get(c) if (lastNode != null) { sb.append(c) } } dfs(lastNode, result, sb) return result } private fun dfs(node: TrieNode?, list: ArrayList<String>, cur: StringBuilder) { if (node?.isWord!!) { list.add(cur.toString()) } if (node.children.isEmpty()) { return } for (child in node.children.values) { dfs(child, list, cur.append(child.char.toString())) //reduce the length for backtracking cur.setLength(cur.length - 1) } } /** * node for TrieTree * */ class TrieNode constructor(c: Char?) { var isWord = false var char: Char? = null val children = HashMap<Char, TrieNode>() constructor() : this(null) init { char = c } fun insert(word: String?) { if (word == null || word.isEmpty()) { return } val first = word[0] var child = children.get(first) if (child == null) { child = TrieNode(first) children.put(first, child) } //insert entire word if (word.length > 1) { child.insert(word.substring(1)) } else { child.isWord = true } } } }