Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit80e3216

Browse files
committed
Add annotations to Trie.
1 parent39acb2b commit80e3216

File tree

3 files changed

+46
-0
lines changed

3 files changed

+46
-0
lines changed

‎src/data-structures/trie/Trie.js‎

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,21 +1,33 @@
11
importTrieNodefrom'./TrieNode';
22

3+
// Character that we will use for trie tree root.
34
constHEAD_CHARACTER='*';
45

56
exportdefaultclassTrie{
67
constructor(){
78
this.head=newTrieNode(HEAD_CHARACTER);
89
}
910

11+
/**
12+
*@param {string} word
13+
*@return {Trie}
14+
*/
1015
addWord(word){
1116
constcharacters=Array.from(word);
1217
letcurrentNode=this.head;
18+
1319
for(letcharIndex=0;charIndex<characters.length;charIndex+=1){
1420
constisComplete=charIndex===characters.length-1;
1521
currentNode=currentNode.addChild(characters[charIndex],isComplete);
1622
}
23+
24+
returnthis;
1725
}
1826

27+
/**
28+
*@param {string} word
29+
*@return {string[]}
30+
*/
1931
suggestNextCharacters(word){
2032
constlastCharacter=this.getLastCharacterNode(word);
2133

@@ -26,17 +38,27 @@ export default class Trie {
2638
returnlastCharacter.suggestChildren();
2739
}
2840

41+
/**
42+
*@param {string} word
43+
*@return {boolean}
44+
*/
2945
doesWordExist(word){
3046
return!!this.getLastCharacterNode(word);
3147
}
3248

49+
/**
50+
*@param {string} word
51+
*@return {TrieNode}
52+
*/
3353
getLastCharacterNode(word){
3454
constcharacters=Array.from(word);
3555
letcurrentNode=this.head;
56+
3657
for(letcharIndex=0;charIndex<characters.length;charIndex+=1){
3758
if(!currentNode.hasChild(characters[charIndex])){
3859
returnnull;
3960
}
61+
4062
currentNode=currentNode.getChild(characters[charIndex]);
4163
}
4264

‎src/data-structures/trie/TrieNode.js‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,29 @@
11
importHashTablefrom'../hash-table/HashTable';
22

33
exportdefaultclassTrieNode{
4+
/**
5+
*@param {string} character
6+
*@param {boolean} isCompleteWord
7+
*/
48
constructor(character,isCompleteWord=false){
59
this.character=character;
610
this.isCompleteWord=isCompleteWord;
711
this.children=newHashTable();
812
}
913

14+
/**
15+
*@param {string} character
16+
*@return {TrieNode}
17+
*/
1018
getChild(character){
1119
returnthis.children.get(character);
1220
}
1321

22+
/**
23+
*@param {string} character
24+
*@param {boolean} isCompleteWord
25+
*@return {TrieNode}
26+
*/
1427
addChild(character,isCompleteWord=false){
1528
if(!this.children.has(character)){
1629
this.children.set(character,newTrieNode(character,isCompleteWord));
@@ -19,14 +32,24 @@ export default class TrieNode {
1932
returnthis.children.get(character);
2033
}
2134

35+
/**
36+
*@param {string} character
37+
*@return {boolean}
38+
*/
2239
hasChild(character){
2340
returnthis.children.has(character);
2441
}
2542

43+
/**
44+
*@return {string[]}
45+
*/
2646
suggestChildren(){
2747
return[...this.children.getKeys()];
2848
}
2949

50+
/**
51+
*@return {string}
52+
*/
3053
toString(){
3154
letchildrenAsString=this.suggestChildren().toString();
3255
childrenAsString=childrenAsString ?`:${childrenAsString}` :'';

‎src/data-structures/trie/__test__/TrieNode.test.js‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,6 +25,7 @@ describe('TrieNode', () => {
2525
trieNode.addChild('o');
2626

2727
expect(trieNode.getChild('a').toString()).toBe('a');
28+
expect(trieNode.getChild('a').character).toBe('a');
2829
expect(trieNode.getChild('o').toString()).toBe('o');
2930
expect(trieNode.getChild('b')).toBeUndefined();
3031
});

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp