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

Commitd25eff4

Browse files
appleJaxtrekhleb
authored andcommitted
Add Trie.deleteWord and TrieNode.removeChild (trekhleb#181)
1 parent6e2ff9b commitd25eff4

File tree

4 files changed

+96
-0
lines changed

4 files changed

+96
-0
lines changed

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

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,35 @@ export default class Trie {
2424
returnthis;
2525
}
2626

27+
/**
28+
*@param {string} word
29+
*@return {Trie}
30+
*/
31+
deleteWord(word){
32+
functiondepthFirstDelete(currentNode,charIndex){
33+
if(charIndex>=word.length)return;
34+
35+
constcharacter=word[charIndex];
36+
constnextNode=currentNode.getChild(character);
37+
38+
if(nextNode==null)return;
39+
40+
depthFirstDelete(nextNode,charIndex+1);
41+
42+
if(charIndex===word.length-1){
43+
nextNode.isCompleteWord=false;
44+
}
45+
46+
// childNode is deleted only if:
47+
// - childNode has NO children
48+
// - childNode.isCompleteWord === false
49+
currentNode.removeChild(character);
50+
}
51+
52+
depthFirstDelete(this.head,0);
53+
returnthis;
54+
}
55+
2756
/**
2857
*@param {string} word
2958
*@return {string[]}

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

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -37,6 +37,31 @@ export default class TrieNode {
3737
returnchildNode;
3838
}
3939

40+
/**
41+
*@param {string} character
42+
*@return {TrieNode}
43+
*/
44+
removeChild(character){
45+
functionisSafeToDelete(node){
46+
return(
47+
node
48+
&&!node.isCompleteWord
49+
&&node.children.getKeys().length===0
50+
);
51+
}
52+
53+
constchildNode=this.getChild(character);
54+
55+
// delete childNode only if:
56+
// - childNode has NO children
57+
// - childNode.isCompleteWord === false
58+
if(isSafeToDelete(childNode)){
59+
this.children.delete(character);
60+
}
61+
62+
returnthis;
63+
}
64+
4065
/**
4166
*@param {string} character
4267
*@return {boolean}

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

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,18 @@ describe('Trie', () => {
2323
expect(trie.head.getChild('c').getChild('a').getChild('t').toString()).toBe('t*');
2424
});
2525

26+
it('should delete words from trie',()=>{
27+
consttrie=newTrie();
28+
29+
trie.addWord('carpet');
30+
trie.addWord('car');
31+
expect(trie.doesWordExist('carpet')).toBe(true);
32+
33+
trie.deleteWord('carpet');
34+
expect(trie.doesWordExist('carpet')).toEqual(false);
35+
expect(trie.doesWordExist('car')).toEqual(true);
36+
});
37+
2638
it('should suggests next characters',()=>{
2739
consttrie=newTrie();
2840

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

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -18,6 +18,36 @@ describe('TrieNode', () => {
1818
expect(trieNode.toString()).toBe('c:a,o');
1919
});
2020

21+
describe('removing child nodes',()=>{
22+
it('should delete child node if the child node has NO children',()=>{
23+
consttrieNode=newTrieNode('c');
24+
trieNode.addChild('a');
25+
expect(trieNode.hasChild('a')).toBe(true);
26+
27+
trieNode.removeChild('a');
28+
expect(trieNode.hasChild('a')).toBe(false);
29+
});
30+
31+
it('should NOT delete child node if the child node has children',()=>{
32+
consttrieNode=newTrieNode('c');
33+
trieNode.addChild('a');
34+
constchildNode=trieNode.getChild('a');
35+
childNode.addChild('r');
36+
37+
trieNode.removeChild('a');
38+
expect(trieNode.hasChild('a')).toEqual(true);
39+
});
40+
41+
it('should NOT delete child node if the child node completes a word',()=>{
42+
consttrieNode=newTrieNode('c');
43+
constIS_COMPLETE_WORD=true;
44+
trieNode.addChild('a',IS_COMPLETE_WORD);
45+
46+
trieNode.removeChild('a');
47+
expect(trieNode.hasChild('a')).toEqual(true);
48+
});
49+
});
50+
2151
it('should get child nodes',()=>{
2252
consttrieNode=newTrieNode('c');
2353

0 commit comments

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