Converting an IEnumerable to a lookup with multiple keys per value

Question

What's the best way to transform an IEnumerable into a lookup- or dictionary-like structure, but with multiple keys per value?
What I'm looking for is something that does roughly the same thing as this, and in a generic way:

var wordsByLetter = new Dictionary<char, HashSet<string>>();
foreach (string word in words)
{
    foreach (char letter in word.Distinct())
    {
        if (!wordsByLetter.ContainsKey(letter))
        {
            wordsByLetter.Add(letter, new HashSet<string>());
        }
        wordsByLetter[letter].Add(word);
    }
}

So the result is a dictionary mapping each letter used to the set of words that contain that letter.
For example, if words contained {"foo", "faz", "zoo"} then the resulting dictionary would contain:

'a' -> {"faz"}
'f' -> {"foo", "faz"}
'o' -> {"foo", "zoo"}
'z' -> {"faz", "zoo"}

I could turn my code example into an extension method, but is there a built-in function or better algorithm to use?

Answer 1

ToLookup is the extension method you need. For example:

var lookup = (from word in words
              from c in word
              select new { Word = word, Character = c }).ToLookup(x => x.Character, x => x.Word);

Answer 2

Have you considered using a Trie instead?

C# implementation of a Trie

Answer 3

Here's a solution using ToDictionary :

var wordsByLetter =
    words.SelectMany(word => word.ToCharArray())
         .Distinct()
         .ToDictionary(
            letter => letter,
            letter => words.Where(word => word.Contains(letter)));

Note that it's certainly less efficient than your code, since the words collection is enumerated once to get the distinct letters, then once for each letter...

---

Update: actually I have a much more efficient suggestion :

var wordsByLetter = 
   (from word in words
    from letter in word
    group word by letter into grp
    select new
    {
        Letter = grp.Key,
        Words = new HashSet<string>(grp)
    })
    .ToDictionary(x => x.Letter, x => x.Words);

It should give exactly the same result as your code

Answer 4

// { foo, faz } -> { f|foo, o|foo, f|faz, a|faz, z|faz }
var pairs = words.SelectMany(w =>
   w.Distinct().Select(l => new { Word = w, Letter = l }));

var map = pairs.ToLookup(p => p.Letter, p => p.Word);