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

Print Friendly, PDF & Email

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.

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

Leave a Reply