JSFiddle - React, Tailwind, and code Playground
HTML
Enter a name: <input name="prefix" type="text">
CSS
body {
margin: 12px;
}
input {
border: 1px solid #C0C0C0;
padding: 2px;
}
JavaScript
var RadixTrie = function(words) {
this.T = {};
this.initialize(words);
};
RadixTrie.prototype = {
initialize: function(words) {
var self = this;
words = words || [];
words.forEach(function(word) {
self.insert(word);
});
},
insert: function(word, T) {
var self = this;
var l = word.length;
var prefix;
word = word && word.toLowerCase();
T = T || this.T;
// Search for existing prefixes
while (l--) {
prefix = word.substr(0, l+1);
if (T[prefix]) {
// Found prefix, moving into subtrie
if (!Object.keys(T[prefix]).length) {
// If one word is a pure subset of another word, the prefix
// should also point to the subset.
T[prefix][""] = {};
}
return this.insert(word.substr(l+1), T[prefix]);
}
}
// No prefix found means insert word and check for prefix collision
var siblings = Object.keys(T);
l = word.length;
var siblingFound = siblings.some(function(sibling) {
var s = 0;
var commonPrefix;
do {
if (sibling[s] != word[s]) {
if (s > 1) {
commonPrefix = sibling.substr(0, s-1);
}
break;
}
} while (s++ < l)
if (commonPrefix) {
// Rearrange trie to move word with prefix collision into new
// common prefix subtrie
T[commonPrefix] = {};
self.insert(sibling.substr(s-1), T[commonPrefix]);
T[commonPrefix][sibling.substr(s-1)] = T[sibling];
self.insert(word.substr(s-1), T[commonPrefix]);
delete T[sibling];
...