Skip to content

Instantly share code, notes, and snippets.

@veleek
Created January 29, 2023 21:28
Show Gist options
  • Save veleek/53bda476504a7e8c46dbc27e9cfa35dd to your computer and use it in GitHub Desktop.
Save veleek/53bda476504a7e8c46dbc27e9cfa35dd to your computer and use it in GitHub Desktop.
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');
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment