trie – My Programming Notes

Tag Archives: trie

C# || How To Find Number Of Valid Words For Each Puzzle Using C#

November 09, 2021 admin No comments

The following is a module with functions which demonstrates how to find the number of valid words for each puzzle using C#.

1. Find Num Of Valid Words – Problem Statement

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.
- For example, if the puzzle is “abcdefg”, then valid words are “faced”, “cabbage”, and “baggage”, while
- invalid words are “beefed” (does not include ‘a’) and “based” (includes ‘s’ which is not in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].

Example 1:

Input: words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] Output: [1,1,3,2,4,0] Explanation: 1 valid word for "aboveyz" : "aaaa" 1 valid word for "abrodyz" : "aaaa" 3 valid words for "abslute" : "aaaa", "asas", "able" 2 valid words for "absoryz" : "aaaa", "asas" 4 valid words for "actresz" : "aaaa", "asas", "actt", "access" There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

Example 2:

Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"] Output: [0,1,3,2,0]

2. Find Num Of Valid Words – Solution

The following is a solution which demonstrates how to find the number of valid words for each puzzle.

This solution uses a Trie to find the number of valid words.





		
		
			2. Find Num Of Valid Words - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of valid words in a puzzle
// ============================================================================
public class Solution {
    public IList<int> FindNumOfValidWords(string[] words, string[] puzzles) {
        // Add words to the Trie
        var trie = new Trie();
        foreach (var word in words) {
            // Get distinct characters in the word and sort it
            var chars = word.Distinct().ToArray();

            // Longer words are never valid
            if (chars.Length <= 7) {
                Array.Sort(chars);
                trie.Insert(new string(chars));
            }
        }

        // Check how many words in the puzzle match in the Trie
        var result = new List<int>();
        foreach (var word in puzzles) {
            result.Add(trie.Search(word));
        }
        return result;
    }

    // Trie
    public class Trie {
        private TrieNode root;

        public Trie() {
            root = new TrieNode();
        }
        public void Insert(string word) {
            var node = root;
            foreach (var ch in word) {
                if (!node.ContainsKey(ch)) {
                    node.Add(ch, new TrieNode());
                }
                node = node.Get(ch);
            }
            node.SetComplete();
        }
        public int Search(string word) {
            return DFS(root, word, false);
        }
        private int DFS(TrieNode node, string word, bool firstFound) {
            var result = firstFound ? node.WordCount() : 0;
            foreach (var ch in word) {
                if (node.ContainsKey(ch)) {
                    result += DFS(node.Get(ch), word, firstFound || ch == word[0]);
                }
            }
            return result;
        }
    }

    // TrieNode
    public class TrieNode {
        private Dictionary<char, TrieNode> children;
        private bool isComplete;
        private int count;

        public TrieNode() {
            children = new Dictionary<char, TrieNode>();
        }
        public bool ContainsKey(char ch) {
            return children.ContainsKey(ch);
        }
        public TrieNode Get(char ch) {
            return children[ch];
        }
        public void Add(char ch, TrieNode node) {
            children[ch] = node;
        }
        public void SetComplete() {
            isComplete = true;
            ++count;
        }
        public bool IsComplete() {
            return isComplete;
        }
        public int WordCount() {
            return count;
        }
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to find number of valid words in a puzzle
// ============================================================================
public class Solution {
    public IList<int> FindNumOfValidWords(string[] words, string[] puzzles) {
        // Add words to the Trie
        var trie = new Trie();
        foreach (var word in words) {
            // Get distinct characters in the word and sort it
            var chars = word.Distinct().ToArray();
 
            // Longer words are never valid
            if (chars.Length <= 7) {
                Array.Sort(chars);
                trie.Insert(new string(chars));
            }
        }
 
        // Check how many words in the puzzle match in the Trie
        var result = new List<int>();
        foreach (var word in puzzles) {
            result.Add(trie.Search(word));
        }
        return result;
    }
 
    // Trie
    public class Trie {
        private TrieNode root;
 
        public Trie() {
            root = new TrieNode();
        }
        public void Insert(string word) {
            var node = root;
            foreach (var ch in word) {
                if (!node.ContainsKey(ch)) {
                    node.Add(ch, new TrieNode());
                }
                node = node.Get(ch);
            }
            node.SetComplete();
        }
        public int Search(string word) {
            return DFS(root, word, false);
        }
        private int DFS(TrieNode node, string word, bool firstFound) {
            var result = firstFound ? node.WordCount() : 0;
            foreach (var ch in word) {
                if (node.ContainsKey(ch)) {
                    result += DFS(node.Get(ch), word, firstFound || ch == word[0]);
                }
            }
            return result;
        }
    }
 
    // TrieNode
    public class TrieNode {
        private Dictionary<char, TrieNode> children;
        private bool isComplete;
        private int count;
 
        public TrieNode() {
            children = new Dictionary<char, TrieNode>();
        }
        public bool ContainsKey(char ch) {
            return children.ContainsKey(ch);
        }
        public TrieNode Get(char ch) {
            return children[ch];
        }
        public void Add(char ch, TrieNode node) {
            children[ch] = node;
        }
        public void SetComplete() {
            isComplete = true;
            ++count;
        }
        public bool IsComplete() {
            return isComplete;
        }
        public int WordCount() {
            return count;
        }
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[1,1,3,2,4,0] [0,1,3,2,0]

C# || How To Implement Trie Prefix Tree Using C#

November 09, 2021 admin No comments

The following is a module with functions which demonstrates how to implement a trie prefix tree using C#.

1. Trie – Problem Statement

A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.

Implement the Trie class:

Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.

Example 1:

Input ["Trie", "insert", "search", "search", "startsWith", "insert", "search"] [[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]] Output [null, null, true, false, true, null, true]
Explanation Trie trie = new Trie(); trie.insert("apple"); trie.search("apple"); // return True trie.search("app"); // return False trie.startsWith("app"); // return True trie.insert("app"); trie.search("app"); // return True

2. Trie – Solution

The following is a solution which demonstrates how to implement a trie prefix tree.





		
		
			2. Trie - Solution
			
C#
			
			// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to implement a trie prefix tree
// ============================================================================
// Trie
public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Add(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetComplete();
    }
    // Search a prefix or whole key in trie and
    // returns the node where search ends
    public TrieNode SearchPrefix(string word) {
        var node = root;
        foreach (var ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        var node = SearchPrefix(word);
        return node != null && node.IsComplete();
    }
    public bool StartsWith(string prefix) {
        var node = SearchPrefix(prefix);
        return node != null;
    }
}

// TrieNode
public class TrieNode {
    private Dictionary<char, TrieNode> children;
    private bool isComplete;
    private int count;

    public TrieNode() {
        children = new Dictionary<char, TrieNode>();
    }
    public bool ContainsKey(char ch) {
        return children.ContainsKey(ch);
    }
    public TrieNode Get(char ch) {
        return children[ch];
    }
    public void Add(char ch, TrieNode node) {
        children[ch] = node;
    }
    public void SetComplete() {
        isComplete = true;
        ++count;
    }
    public bool IsComplete() {
        return isComplete;
    }
    public int WordCount() {
        return count;
    }
}// http://programmingnotes.org/
			
				
					
				
					1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
				
						// ============================================================================
//    Author: Kenneth Perkins
//    Date:   Nov 9, 2021
//    Taken From: http://programmingnotes.org/
//    File:  Solution.cs
//    Description: Demonstrates how to implement a trie prefix tree
// ============================================================================
// Trie
public class Trie {
    private TrieNode root;
 
    public Trie() {
        root = new TrieNode();
    }
    public void Insert(string word) {
        var node = root;
        foreach (var ch in word) {
            if (!node.ContainsKey(ch)) {
                node.Add(ch, new TrieNode());
            }
            node = node.Get(ch);
        }
        node.SetComplete();
    }
    // Search a prefix or whole key in trie and
    // returns the node where search ends
    public TrieNode SearchPrefix(string word) {
        var node = root;
        foreach (var ch in word) {
            if (node.ContainsKey(ch)) {
                node = node.Get(ch);
            } else {
                return null;
            }
        }
        return node;
    }
    public bool Search(string word) {
        var node = SearchPrefix(word);
        return node != null && node.IsComplete();
    }
    public bool StartsWith(string prefix) {
        var node = SearchPrefix(prefix);
        return node != null;
    }
}
 
// TrieNode
public class TrieNode {
    private Dictionary<char, TrieNode> children;
    private bool isComplete;
    private int count;
 
    public TrieNode() {
        children = new Dictionary<char, TrieNode>();
    }
    public bool ContainsKey(char ch) {
        return children.ContainsKey(ch);
    }
    public TrieNode Get(char ch) {
        return children[ch];
    }
    public void Add(char ch, TrieNode node) {
        children[ch] = node;
    }
    public void SetComplete() {
        isComplete = true;
        ++count;
    }
    public bool IsComplete() {
        return isComplete;
    }
    public int WordCount() {
        return count;
    }
}// http://programmingnotes.org/

QUICK NOTES:
The highlighted lines are sections of interest to look out for.

The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.

Once compiled, you should get this as your output for the example cases:

[null,null,true,false,true,null,true]

Tag Archives: trie

C# || How To Find Number Of Valid Words For Each Puzzle Using C#

C# || How To Implement Trie Prefix Tree Using C#

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories