Last active
May 25, 2017 22:20
-
-
Save coderek/2845a6c74d33a9089ad12a87f5709299 to your computer and use it in GitHub Desktop.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| <!DOCTYPE html> | |
| <html> | |
| <head> | |
| <meta charset="utf-8"> | |
| <title>index</title> | |
| </head> | |
| <body> | |
| <label for="Input">Input</label> | |
| <input type="text" name="Input" value="" id="Input"> | |
| <ul id="suggestions"> | |
| </ul> | |
| <script src="typeahead.js"></script> | |
| </body> | |
| </html> |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| document.body.onload = function () { | |
| const codeA = 'a'.charCodeAt(0); | |
| class Trie { | |
| constructor() { | |
| this.root = { | |
| children: new Array(26).fill(null), | |
| isWord: null | |
| }; | |
| } | |
| insert(word) { | |
| let node = this.root; | |
| for (let i=0;i<word.length;i++) { | |
| let code = word.charCodeAt(i); | |
| if (node.children[code-codeA] == null) { | |
| let newNode = { | |
| children: new Array(26).fill(null), | |
| isWord: null | |
| }; | |
| node.children[code-codeA] = newNode; | |
| node = newNode; | |
| } else { | |
| node = node.children[code-codeA]; | |
| } | |
| } | |
| node.isWord = word; | |
| } | |
| prefixMatch(word) { | |
| let node = this.root; | |
| for (let i=0;i<word.length;i++) { | |
| let code = word.charCodeAt(i); | |
| if (node.children[code-codeA] == null) { | |
| return []; | |
| } else { | |
| node = node.children[code-codeA]; | |
| } | |
| } | |
| return this.dfs(node); | |
| } | |
| dfs(node) { | |
| let ret = []; | |
| function _dfs(node, ret) { | |
| if (node == null) return; | |
| if (node.isWord!=null) { | |
| ret.push(node.isWord); | |
| } | |
| for (let i=0;i<26;i++) { | |
| _dfs(node.children[i], ret); | |
| } | |
| } | |
| _dfs(node, ret); | |
| return ret; | |
| } | |
| } | |
| let words = [ | |
| "zeng", | |
| "qiang", | |
| "xiao", | |
| "ni", | |
| "lai", | |
| "lala", | |
| "zen", | |
| "zengqiang" | |
| ]; | |
| let trie = new Trie(); | |
| for (let w of words) { | |
| trie.insert(w); | |
| } | |
| let input = document.getElementById("Input"); | |
| input.addEventListener('keyup', function () { | |
| let suggestions = trie.prefixMatch(input.value); | |
| render(suggestions); | |
| }); | |
| function render(suggestions) { | |
| let suggestionsEl = document.getElementById('suggestions'); | |
| while (suggestionsEl.firstChild) { | |
| suggestionsEl.removeChild(suggestionsEl.firstChild); | |
| } | |
| for (let su of suggestions) { | |
| let li = document.createElement('li'); | |
| li.innerHTML = su; | |
| suggestionsEl.appendChild(li); | |
| } | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment