Find in the List of words with letters in certain positions

November 11, 2021

I’m doing a crossword puzzle maker. The user selects cells for words, and the program compiles a crossword puzzle from the dictionary (all words which can be used in the crossword) – List<string>.

I need to find a word (words) in a dictionary which matches given mask (pattern).

For example, I need to find all words which match

#a###g

pattern, i.e. all words of length 6 in the dictionary with "a" at index 1 and "g" at index 5

The number of letters and their position are unknown in advance

How do I realize this?

>Solution :

You can convert word description (mask)

 #a###g

into corresponding regular expression pattern:

 ^\p{L}a\p{L}{3}g$

Pattern explained:

 ^        - anchor, word beginning
 \p{L}    - arbitrary letter
 a        - letter 'a'
 \p{L}{3} - exactly 3 arbitrary letters
 g        - letter 'g'
 $        - anchor, word ending

and then get all words from dictionary which match this pattern:

Code:

using System.Linq;
using System.Text.RegularExpressions;

...

private static string[] Variants(string mask, IEnumerable<string> availableWords) {
  Regex regex = new Regex("^" + Regex.Replace(mask, "#*", m => @$"\p{{L}}{{{m.Length}}}") + "$");

  return availableWords
    .Where(word => regex.IsMatch(availableWords))
    .OrderBy(word => word)
    .ToArray();
}

Demo:

string[] allWords = new [] {
  "quick",
  "brown",
  "fox",
  "jump",
  "rating",
  "coding"
  "lazy",
  "paring",
  "fang",
  "dog", 
};

string[] variants = Variants("#a###g", allWords);

Console.Write(string.Join(Environment.NewLine, variants));

Outcome: