What is it?
Autocomplete or suggestion or typeahead offers a number of possible values while typing. This usually applies to search bar and fill in form; such as city, state, country, etc.
Problem
In a survey form, participants need to type in their current state in a given text field. Given a list of 50 states. How can we increase the participants' typing speed and help them decrease the number of keystrokes to fill in the state? It must be case insenitive.
const states = [
'Alabama', 'Alaska', 'Arizona', 'Arkansas', 'California', 'Colorado', 'Connecticut',
'Delaware', 'Florida', 'Georgia', 'Hawaii', 'Idaho', 'Illinois', 'Indiana', 'Iowa', 'Kansas',
'Kentucky', 'Louisiana', 'Maine', 'Maryland', 'Massachusetts', 'Michigan', 'Minnesota',
'Mississippi', 'Missouri', 'Montana', 'Nebraska', 'Nevada', 'New Hampshire', 'New Jersey',
'New Mexico', 'New York', 'North Carolina', 'North Dakota', 'Ohio', 'Oklahoma', 'Oregon',
'Pennsylvania', 'Rhode Island', 'South Carolina', 'South Dakota', 'Tennessee', 'Texas', 'Utah',
'Vermont', 'Virginia', 'Washington', 'West Virginia', 'Wisconsin', 'Wyoming'
];
If the participant didn't type in anything, it should return:
[]
If the participant type in 'q', it should return:
[]
If the participant type in 'n', it should return:
['Nebraska', 'Nevada', 'New Hampshire', 'New Jersey', 'New Mexico', 'New York', 'North Carolina', 'North Dakota']
If the participant type in 'ne', it should return:
['Nebraska', 'Nevada', 'New Hampshire', 'New Jersey', 'New Mexico', 'New York']
If the participant type in 'new', it should return:
['New Hampshire', 'New Jersey', 'New Mexico', 'New York']
If the participant type in 'new y', it should return:
['New York']
Brute Force Solution
We are going to declare an empty array that holds all the possible states. Next, We iterate each state (50 states) and check if the state starts with the user's input. If so, add it to the array that we declare earlier and later return it.
class Autocomplete {
constructor(list) {
this.list = list;
}
/**
* Check if the string starts with another string
* @param {string} word
* @param {string} input
* @return {boolean} whether or not the word starts with input
* @time complexity O(1)
* @space complexity O(1)
*/
static isStartsWith(word, input) {
return word.toUpperCase().startsWith(input.toUpperCase());
}
/**
* Get an array of possible values
* @param {string} input
* @return {string[]} an array of possible values
* @time complexity O(M) where M is the size of list
* @space complexity O(M) where M is the size of list
*/
getAutocompleteList(input) {
if (!input) {
return [];
}
const possibleValues = [];
for (let i = 0; i < this.list.length; i++) {
if (Autocomplete.isStartsWith(this.list[i], input)) {
possibleValues.push(this.list[i]);
}
}
return possibleValues;
}
}
Test Brute Force Solution
Let's test it using jest.
describe('Brute Force', () => {
let autocomplete;
beforeAll(() => {
autocomplete = new Autocomplete(states);
});
test('should return an array', () => {
const result = autocomplete.getAutocompleteList('');
expect(result).toBeInstanceOf(Array);
});
test('should return an empty array when there is no match', () => {
const result = autocomplete.getAutocompleteList('q');
expect(result).toHaveLength(0);
});
test('should return a list of possible values', () => {
const result = autocomplete.getAutocompleteList('New');
const expected = [ 'New Hampshire', 'New Jersey', 'New Mexico', 'New York' ];
expect(result).toEqual(expected);
});
test('should return an array containing exact one element', () => {
const result = autocomplete.getAutocompleteList('New York');
const expected = [ 'New York' ];
expect(result).toEqual(expected);
});
});
Brute Force
✓ should return an array (1 ms)
✓ should return an empty array when there is no match
✓ should return a list of possible values (1 ms)
✓ should return an array containing exact one element
Trie Data Structure Solution
What is trie?
In computer science, a trie, also called digital tree or prefix tree, is a kind of search tree—an ordered tree data structure used to store a dynamic set or associative array where the keys are usually strings.Wikipedia
First of all, we construct a trie data structure using object. Next, we search for user's input from the root of the trie using depth of search (dfs) or breath of search (bfs) algorithm. In this example, we will implement both algorithms. If the search is found, then return the rest of the word in an array.
Let's get started with creating a trie data structure. A trie would look like this. The graph below illustrates a trie for Apple, App, Car, Cat, and Case.
class TrieNode {
constructor() {
// CONTAINS ZERO OR MORE CHILDREN
this.children = {};
// INDICATE WHETHER THIS IS THE END OF A WORD
this.last = false;
}
}
class Autocomplete {
constructor(list) {
// INITIALIZE THE ROOT
this.root = this.buildTrie(list);
}
/**
* BUILD A TRIE DATA STRUCTURE
* @param {string[]} list An array of words
* @return {TrieNode}
* @time complexity: O(N M) where N is the size of the list, M is the length of the words in the list
* @space complexity: O(N M) where N is the size of the list, M is the length of the words in the list
*/
buildTrie(list) {
// THE ROOT OF THE TREE
const root = new TrieNode();
// FOR EACH WORD
for (const word of list) {
// ADD TO THE ROOT
this.insert(root, word);
}
return root;
}
/**
* INSERT A CHILD NODE TO THE PARENT NODE
* A CHILD NODE IS CONSTRUCTED BASE ON EACH CHARACTER IN THE GIVEN WORD
* @param {TrieNode} node
* @param {string} word
* @time complexity: O(N) where N is the size of word
* @space complexity: O(N) where N is the size of word
*/
insert(parent, word) {
// ITERATE EACH CHARACTER IN THE WORD
for (const char of word) {
// ADD A CHILD IF IT DOES NOT EXIST
if (parent.children[char] === undefined) {
parent.children[char] = new TrieNode();
}
// SET THE CURRENT CHILD AS PARENT
parent = parent.children[char];
}
// SET TO TRUE BECAUSE THIS IS THE END OF THE WORD
parent.last = true;
}
}
When we create an instance of Autocomplete with a list of states, it will create a trie.
const autocomplete = new Autocomplete(states);
Let's write a test for it.
describe('Autocomplete using Trie', () => {
test('should build a trie', () => {
const words = [
'apple',
'cat',
'car',
'app',
];
const autocomplete = new Autocomplete(words);
const result = JSON.stringify(autocomplete.root);
const expected = JSON.stringify({
children: {
a: {
children: {
p: {
children: {
p: {
children: {
l: {
children: {
e: {
children: {},
last: true,
},
},
last: false,
},
},
last: true,
},
},
last: false,
},
},
last: false,
},
c: {
children: {
a: {
children: {
t: {
children: {},
last: true,
},
r: {
children: {},
last: true,
},
},
last: false,
},
},
last: false,
}
},
last: false,
});
expect(result).toEqual(expected);
});
});
Autocomplete using Trie
✓ should build a trie (2 ms)
Next, we are going to write a function that check whether it starts with a given word.
/**
* @typeof {object} StartsWithResult
* @param {TrieNode} node
* @param {string} word
*/
/**
* CHECK IF THERE IS A TRIE STARTS WITH THE INPUT
* @param {string} input
* @return {StartsWithResult}
* @time complexity O(N) where N is the size of input
* @space complexity O(N) where N is the size of input
*/
isStartsWith(input) {
let node = this.root,
found = true,
word = '';
for (const char of input) {
// CHECK IF THE CHARACTER EXIST
if (node.children[char]) {
node = node.children[char];
word += char;
} else if (node.children[char.toUpperCase()]) { // CASE INSENITIVE
node = node.children[char.toUpperCase()];
word += char.toUpperCase();
} else {
found = false;
break;
}
}
// RETURNS THE CURRENT NODE AND WORD
return {
node: (found ? node : null),
word,
};
}
Depth First Search
Now, we have our trie data structure. Let's write a function to get a list of suggestion. There are two ways of traversing a trie; they are depth first search and breath first search.
Let's implement depth first search.
/**
* GET AN ARRAY OF SUGGESTIONS
* @param {string} input
* @return {string[]}
* @time complexity: O(N) where N is the size of input
* @space complexity: O(N) where N is the size of input
*/
getAutocompleteListDfs(input) {
// CHECK IF IT STARTS WITH INPUT
const { node, word } = this.isStartsWith(input);
// RETURN EMPTY ARRAY IF NO MATCH
if (!node) {
return [];
}
const words = [];
// ADD TO THE RESULT IF THE CURRENT NODE ALSO THE LAST OF A WORD
if (node.last) {
words.push(word);
}
return words.concat(this.getWordsDepthFirstSearch(word, node));
}
/**
* GET ALL THE WORDS FROM THE GIVEN NODE
* USING DEPTH FIRST SEARCH ALGORITHM
* @param {string} prefix
* @param {TrieNode} node
* @return {string[]} An array of words
* @time complexity: O(N) where N is the size of node
* @space complexity: O(N) where N is the size of node
*/
getWordsDepthFirstSearch(prefix, node) {
if (!node) {
return;
}
let words = [];
for (const char in node.children) {
// IF THIS IS THE END OF THE WORD
if (node.children[char].last) {
// CONCATENATE THE PREVIOUS CHARACTERS AND THE CURRENT CHARACTER
// ADD IT TO THE WORDS
words.push(prefix + char);
}
words = [
...words,
...this.getWordsDepthFirstSearch(prefix + char, node.children[char]) // RECURSIVELY GET THE REST OF THE CHARACTERS
];
}
return words;
}
Breath First Search
/**
* GET AN ARRAY OF SUGGESTIONS
* @param {string} input
* @return {string[]}
* @time complexity: O(N) where N is the size of input
* @space complexity: O(N) where N is the size of input
*/
getAutocompleteListBfs(input) {
// CHECK IF IT STARTS WITH INPUT
const { node, word } = this.isStartsWith(input);
// RETURN EMPTY ARRAY IF NO MATCH
if (!node) {
return [];
}
const words = [];
// ADD TO THE RESULT IF THE CURRENT NODE ALSO THE LAST OF A WORD
if (node.last) {
words.push(word);
}
return words.concat(this.getWordsBreathFirstSearch(word, node));
}
/**
* GET ALL THE WORDS FROM THE GIVEN NODE
* USING BREATH FIRST SEARCH ALGORITHM
* @param {string} prefix
* @param {TrieNode} node
* @return {string[]} An array of words
* @time complexity: O(N) where N is the size of node
* @space complexity: O(N) where N is the size of node
*/
getWordsBreathFirstSearch(prefix, node) {
const words = [];
const queue = [
{ node, prefix }
];
while (queue.length) {
const { node, prefix } = queue.shift();
for (const key in node.children) {
// IF THIS IS THE END OF THE WORD
if (node.children[key].last) {
// CONCATENATE THE PREVIOUS CHARACTERS AND THE CURRENT CHARACTER
// ADD IT TO THE WORDS
words.push(prefix + key);
}
// ADD TO THE QUEUE
queue.push({
node: node.children[key],
prefix: prefix + key,
});
}
}
return words;
}
Full Code
class TrieNode {
constructor() {
// CONTAINS ZERO OR MORE CHILDREN
this.children = {};
// INDICATE WHETHER THIS IS THE END OF A WORD
this.last = false;
}
}
class Autocomplete {
constructor(list) {
// INITIALIZE THE ROOT
this.root = this.buildTrie(list);
}
/**
* BUILD A TRIE DATA STRUCTURE
* @param {string[]} list An array of words
* @return {TrieNode}
* @time complexity: O(N M) where N is the size of the list, M is the length of the words in the list
* @space complexity: O(N M) where N is the size of the list, M is the length of the words in the list
*/
buildTrie(list) {
// THE ROOT OF THE TREE
const root = new TrieNode();
// FOR EACH WORD
for (const word of list) {
// ADD TO THE ROOT
this.insert(root, word);
}
return root;
}
/**
* INSERT A CHILD NODE TO THE PARENT NODE
* A CHILD NODE IS CONSTRUCTED BASE ON EACH CHARACTER IN THE GIVEN WORD
* @param {TrieNode} node
* @param {string} word
* @time complexity: O(N) where N is the size of word
* @space complexity: O(N) where N is the size of word
*/
insert(parent, word) {
// ITERATE EACH CHARACTER IN THE WORD
for (const char of word) {
// ADD A CHILD IF IT DOES NOT EXIST
if (parent.children[char] === undefined) {
parent.children[char] = new TrieNode();
}
// SET THE CURRENT CHILD AS PARENT
parent = parent.children[char];
}
// SET TO TRUE BECAUSE THIS IS THE END OF THE WORD
parent.last = true;
}
/**
* @typeof {object} StartsWithResult
* @param {TrieNode} node
* @param {string} word
*/
/**
* CHECK IF THERE IS A TRIE STARTS WITH THE INPUT
* @param {string} input
* @return {StartsWithResult}
* @time complexity O(N) where N is the size of input
* @space complexity O(N) where N is the size of input
*/
isStartsWith(input) {
let node = this.root,
found = true,
word = '';
for (const char of input) {
// CHECK IF THE CHARACTER EXIST
if (node.children[char]) {
node = node.children[char];
word += char;
} else if (node.children[char.toUpperCase()]) { // CASE INSENITIVE
node = node.children[char.toUpperCase()];
word += char.toUpperCase();
} else {
found = false;
break;
}
}
// RETURNS THE CURRENT NODE AND WORD
return {
node: (found ? node : null),
word,
};
}
/**
* GET AN ARRAY OF SUGGESTIONS
* @param {string} input
* @return {string[]}
* @time complexity: O(N) where N is the size of input
* @space complexity: O(N) where N is the size of input
*/
getAutocompleteListDfs(input) {
// CHECK IF IT STARTS WITH INPUT
const { node, word } = this.isStartsWith(input);
// RETURN EMPTY ARRAY IF NO MATCH
if (!node) {
return [];
}
const words = [];
// ADD TO THE RESULT IF THE CURRENT NODE ALSO THE LAST OF A WORD
if (node.last) {
words.push(word);
}
return words.concat(this.getWordsDepthFirstSearch(word, node));
}
/**
* GET AN ARRAY OF SUGGESTIONS
* @param {string} input
* @return {string[]}
* @time complexity: O(N) where N is the size of input
* @space complexity: O(N) where N is the size of input
*/
getAutocompleteListBfs(input) {
// CHECK IF IT STARTS WITH INPUT
const { node, word } = this.isStartsWith(input);
// RETURN EMPTY ARRAY IF NO MATCH
if (!node) {
return [];
}
const words = [];
// ADD TO THE RESULT IF THE CURRENT NODE ALSO THE LAST OF A WORD
if (node.last) {
words.push(word);
}
return words.concat(this.getWordsBreathFirstSearch(word, node));
}
/**
* GET ALL THE WORDS FROM THE GIVEN NODE
* USING DEPTH FIRST SEARCH ALGORITHM
* @param {string} prefix
* @param {TrieNode} node
* @return {string[]} An array of words
* @time complexity: O(N) where N is the size of node
* @space complexity: O(N) where N is the size of node
*/
getWordsDepthFirstSearch(prefix, node) {
if (!node) {
return;
}
let words = [];
for (const char in node.children) {
// IF THIS IS THE END OF THE WORD
if (node.children[char].last) {
// CONCATENATE THE PREVIOUS CHARACTERS AND THE CURRENT CHARACTER
// ADD IT TO THE WORDS
words.push(prefix + char);
}
words = [
...words,
...this.getWordsDepthFirstSearch(prefix + char, node.children[char]) // RECURSIVELY GET THE REST OF THE CHARACTERS
];
}
return words;
}
/**
* GET ALL THE WORDS FROM THE GIVEN NODE
* USING BREATH FIRST SEARCH ALGORITHM
* @param {string} prefix
* @param {TrieNode} node
* @return {string[]} An array of words
* @time complexity: O(N) where N is the size of node
* @space complexity: O(N) where N is the size of node
*/
getWordsBreathFirstSearch(prefix, node) {
const words = [];
const queue = [
{ node, prefix }
];
while (queue.length) {
const { node, prefix } = queue.shift();
for (const key in node.children) {
// IF THIS IS THE END OF THE WORD
if (node.children[key].last) {
// CONCATENATE THE PREVIOUS CHARACTERS AND THE CURRENT CHARACTER
// ADD IT TO THE WORDS
words.push(prefix + key);
}
// ADD TO THE QUEUE
queue.push({
node: node.children[key],
prefix: prefix + key,
});
}
}
return words;
}
}
What are the difference between depth first search and breath first search?
Obviously, the result come from these two algoritms are quite different. The list of suggestions returned from depth first search are in order as they pass in to the consturctor. Whereas, the result returned from breath first search are from shortest to longest words.
Test Trie Solution
const states = [
'Alabama', 'Alaska', 'Arizona', 'Arkansas', 'California', 'Colorado', 'Connecticut',
'Delaware', 'Florida', 'Georgia', 'Hawaii', 'Idaho', 'Illinois', 'Indiana', 'Iowa', 'Kansas',
'Kentucky', 'Louisiana', 'Maine', 'Maryland', 'Massachusetts', 'Michigan', 'Minnesota',
'Mississippi', 'Missouri', 'Montana', 'Nebraska', 'Nevada', 'New Hampshire', 'New Jersey',
'New Mexico', 'New York', 'North Carolina', 'North Dakota', 'Ohio', 'Oklahoma', 'Oregon',
'Pennsylvania', 'Rhode Island', 'South Carolina', 'South Dakota', 'Tennessee', 'Texas', 'Utah',
'Vermont', 'Virginia', 'Washington', 'West Virginia', 'Wisconsin', 'Wyoming'
];
describe('Autocomplete using Trie', () => {
let autocomplete;
beforeAll(() => {
autocomplete = new Autocomplete(states);
});
test('should build a trie', () => {
const words = [
'apple',
'cat',
'car',
'app',
];
const autocomplete = new Autocomplete(words);
const result = JSON.stringify(autocomplete.root);
const expected = JSON.stringify({
children: {
a: {
children: {
p: {
children: {
p: {
children: {
l: {
children: {
e: {
children: {},
last: true,
},
},
last: false,
},
},
last: true,
},
},
last: false,
},
},
last: false,
},
c: {
children: {
a: {
children: {
t: {
children: {},
last: true,
},
r: {
children: {},
last: true,
},
},
last: false,
},
},
last: false,
}
},
last: false,
});
expect(result).toEqual(expected);
});
describe('Depth First Search', () => {
test('should return an array', () => {
const result = autocomplete.getAutocompleteListDfs('');
expect(result).toBeInstanceOf(Array);
});
test('should return an empty array when there is no match', () => {
const result = autocomplete.getAutocompleteListDfs('q');
expect(result).toHaveLength(0);
});
test('should return a list of possible values', () => {
const result = autocomplete.getAutocompleteListDfs('New');
const expected = [ 'New Hampshire', 'New Jersey', 'New Mexico', 'New York' ];
expect(result).toEqual(expected);
});
test('should return an array containing exact one element', () => {
const result = autocomplete.getAutocompleteListDfs('New York');
const expected = [ 'New York' ];
expect(result).toEqual(expected);
});
});
describe('Breath First Search', () => {
test('should return an array', () => {
const result = autocomplete.getAutocompleteListBfs('');
expect(result).toBeInstanceOf(Array);
});
test('should return an empty array when there is no match', () => {
const result = autocomplete.getAutocompleteListBfs('q');
expect(result).toHaveLength(0);
});
test('should return a list of possible values', () => {
const result = autocomplete.getAutocompleteListBfs('New');
const expected = [ 'New York', 'New Jersey', 'New Mexico', 'New Hampshire' ];
expect(result).toEqual(expected);
});
test('should return an array containing exact one element', () => {
const result = autocomplete.getAutocompleteListBfs('New York');
const expected = [ 'New York' ];
expect(result).toEqual(expected);
});
});
});
Autocomplete using Trie
✓ should build a trie (2 ms)
Depth First Search
✓ should return an array (1 ms)
✓ should return an empty array when there is no match
✓ should return a list of possible values (1 ms)
✓ should return an array containing exact one element
Breath First Search
✓ should return an array (1 ms)
✓ should return an empty array when there is no match
✓ should return a list of possible values
✓ should return an array containing exact one element
Conclusion
The trie solution performs better than brute force solution. This is because of their time complexity. In the survey form scenario, for every keystroke, the brute force solution will run 50 times (for each state); however, the trie solution will run the number of times based on the number of characters.
