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]

Was this article helpful?

👍 YesNo

Posted in: C#, Console Tags: c-sharp, leetcode, trie

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

Related

Leave a ReplyCancel reply

Search

Compile Your Code Now

Translate Page

Popular Pages

Recent

Archives

Categories