Solution for LeetCode problem 1178: https://leetcode.com/problems/number-of-valid-words-for-each-puzzle

leetcode-1178.cs

public class Solution
{
	public IList<int> FindNumOfValidWords(string[] words, string[] puzzles)
	{
        // Create a tree with all the words
		var root = Node.PopulateWords(words);

		int[] result = new int[puzzles.Length];
		for (var i = 0; i < puzzles.Length; i++)
		{
			var puzzle = puzzles[i];
			var matches = root.Lookup(puzzle);
            // For each puzzle that matches, we need to grab the count of that word in the words list
            // because there can be duplicates.  Then we can just sum the counts all together.  This
            // could potentially be optimized (or simplified a bit) by storing the counts inline, but
            // it's easy enough to do it this way.
			result[i] = matches.Select(m => root.wordCounts[m]).Sum();
		}

		return result;
	}
}


public class Node
{
	/// <summary>Pointers to the next nodes for each letter</summary>
	public Node[] next = new Node[26];
	
    /// <summary>A mapping of words to the count of that word in the word list</summary>
	public Dictionary<string, int> wordCounts;
	
	/// <summary>All of the words which contain all of the letters so far in the tree</summary>
	public List<string> matches = new List<string>();

	public Node this[char c] => this.next[toIndex(c)];

    // When we're populating the tree initially, we need to create nodes so this helps create them if they don't exist
    // so we can only populate the portions of the tree that aren't empty.
	public Node GetOrCreate(char c)
	{
		var i = toIndex(c);
		Node n = this.next[i];
		if (n == null)
		{
			n = new Node();
			this.next[i] = n;
		}

		return n;
	}

	public void IndexWord(string word)
	{
		var uniqueLetters = word.Distinct().OrderBy(l => l).ToArray();

		// Index this word under each letter so that we can get all words that contain the first letter of the puzzle.
		foreach (var l in uniqueLetters)
		{
			var curr = this[l];
			foreach(var ll in uniqueLetters)
			{
				curr = curr.GetOrCreate(ll);
			}
			curr.matches.Add(word);
		}
	}

	public List<string> Lookup(string puzzle)
	{
		// We only care about words that contain the first letter of the puzzle, so grab that node.
		var curr = this[puzzle[0]];

		// Then for that tree, loop down through it using each letter.  One we get to the end of the word
		// the matches for that node (and all parent nodes in the path) will contain all the words whose
		// letters were all contained in the given puzzle
		var uniqueLetters = puzzle.Distinct().OrderBy(l => l).ToArray();
		var matches = new List<string>();
		
		for(var i = 0; i < uniqueLetters.Length; i++)
		{
			matches.AddRange(curr.LookupInternal(uniqueLetters, i));
		}
		
		return matches.Distinct().ToList();
	}
	
	public List<string> LookupInternal(char[] uniqueLetters, int index) {
		var m = new List<string>(this.matches);
		
		if(index >= uniqueLetters.Length) return m;

		var currentLetter = uniqueLetters[index];
		var curr = this[currentLetter];
		// If curr is null that means that there are no more words that contain currentLetter
		// so we can short circuit and return whatever matches we've found so far.
		if (curr != null)
		{
			// If there _are_ some words that contain the current letter, then let's continue
			// diving down the tree using the next letter
			for (var i = index + 1; i <= uniqueLetters.Length; i++)
			{
				var subMatches = curr.LookupInternal(uniqueLetters, i);
				m.AddRange(subMatches);
			}
		}
		
		return m;
	}

	public static Node PopulateWords(string[] words)
	{
		Node root = new Node();
		root.wordCounts = new Dictionary<string, int>();

		// Initialize a sub-node for each letter of the alphabet
		foreach (var l in "abcdefghijklmnopqrstuvwxyz")
		{
			root.next[toIndex(l)] = new Node();
		}

		// For each word
		foreach (var wg in words.GroupBy(w => w))
		{
			var w = wg.Key;
			var c = wg.Count();
			
			root.wordCounts[w] = c;
			root.IndexWord(w);
		}

		return root;

	}

	public static Func<char, int> toIndex = (char c) => (int)c - (int)'a';
	public static Func<int, char> toChar = (int i) => (char)(i + (int)'a');
}