CODEWITHSUNDEEP
c#
re.m7
re.m7

Reputation: 85

Find words in wordlist from random string of characters

I am working on an unscramble type program where a user is able to input random letters and the program iterates through the letters and a wordlist to try and find words that contain these some or all random letters in the wordlist.

For example:

if Input = "sasdfle"
words found in wordlist = "sad", "fleas", "flea", etc...

Words can only contains letters that are input from the user and each letter cant be repeated. I have found multiple questions on here that find anagrams but I cant seem to find an algorithm that will do what I stated above.

I don't want to post the whole code here but here is the main part that I am having trouble with:

Upvotes: 3

Views: 1576

Answers (1)

Dmitrii Bychenko
Dmitrii Bychenko

Reputation: 186678

Providing that you have an appropriate English words collection, e.g. 

private static HashSet<String> s_Words = new HashSet<String>() {
  "abacus",
  //...
  "flea",
  "fleas",
  //...
  "sad",
  "sea",
  // ...
  "zoom",
};

you can convert it into more convenient aggregated dictionary with key being an initial string with all letters sorted within it ("flea" => "aefl", "sad" => "ads" etc.). If two or more words have the same key, they should be combined into a collection, say, an array: 

"ale", "lea" => "ael" : ["ale", "lea"]

You can implement such a dictionary via Linq:

private static Dictionary<String, String[]> s_Dict = s_Words
  .Select(word => new {
    Key = String.Concat(word.OrderBy(c => c)),
    Value = word})
  .GroupBy(item => item.Key, item => item.Value)
  .ToDictionary(chunk => chunk.Key, chunk => chunk.ToArray());

Then given a string 

String Input = "sasdfle"

all you need to do is to sort it and check just 256 (2 ** (length + 1) == 256) combinations including and excuding each letter:

string source = String.Concat(Input.OrderBy(c => c)); 

// all combinations of the set with empty one excluded, see
// http://stackoverflow.com/questions/30081908/c-sharp-linq-combinatorics-all-combinations-of-a-set-without-the-empty-set/30082360#30082360  
var result = Enumerable
  .Range(1, (1 << source.Length) - 1)
  .Select(index => string.Concat(source.Where((item, idx) => ((1 << idx) & index) != 0)))
  .SelectMany(key => {
     String[] words;

     if (s_Dict.TryGetValue(key, out words))
       return words;
     else
       return new String[0]; })
  .Distinct() // some words can be built in many ways
  .OrderBy(word => word);
//.ToArray(); // if you want to represent words as array

Test

Console.Write(String.Join(Environment.NewLine, result));

will return

flea
fleas
sad
sea

Upvotes: 3

Related Questions