Write a program to find the longest word made of other words

Question

This is my solution to the problem in the title. The code is pretty straightforward. The one problem is with substring; it's \$O(n)\$ in .Net and creates garbage. Any other improvements?

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace LongestWordFromWords
{
    internal class Program
    {
        public static string FindLongestWords(string[] listOfWords)
        {
            if (listOfWords == null) throw new ArgumentException("listOfWords");
            var sortedWords = listOfWords.OrderByDescending(word => word.Length).ToList();
            var dict = new HashSet<String>(sortedWords);
            foreach (var word in sortedWords)
            {
                if (isMadeOfWords(word, dict))
                {
                    return word;
                }
            }
            return null;
        }

        private static bool isMadeOfWords(string word, HashSet<string> dict)
        {
            if (String.IsNullOrEmpty(word)) return false;
            if (word.Length == 1)
            {
                if (dict.Contains(word)) return true;
                else return false;
            }
            foreach (var pair in generatePairs(word))
            {
                if (dict.Contains(pair.Item1))
                {
                    if (dict.Contains(pair.Item2))
                    {
                        return true;
                    }
                    else
                    {
                        return isMadeOfWords(pair.Item2, dict);
                    }
                }
            }
            return false;
        }

        private static List<Tuple<string, string>> generatePairs(string word)
        {
            var output = new List<Tuple<string, string>>();
            for (int i = 1; i < word.Length; i++)
            {
                output.Add(Tuple.Create(word.Substring(0, i), word.Substring(i)));
            }
            return output;
        }

        private static void Main(string[] args)
        {
            string[] listOfWords = { "ala", "ma", "kota", "aa", "aabbb", "bbb", "cccc", "aabbbmacccc", "aabbbmaxxcccc" };
            string longest = FindLongestWords(listOfWords);
            Console.WriteLine(longest);
            string[] listOfWords2 = { "cat", "cats", "catsdogcats", "catxdogcatsrat", "dog", "dogcatsdog",
                                      "hippopotamuses", "rat", "ratcatdogcat" };
            Console.WriteLine(FindLongestWords(listOfWords2));
        }
    }
}

Answer 1

The first thing that strikes me is that you've put everything within the Program class, which forces your methods to be static, and any program where everything is static is a program I want to rewrite :)

Let's start with FindLongestWords(string[]):

if (listOfWords == null) throw new ArgumentException("listOfWords");

This guard clause is throwing the wrong exception, it should be an ArgumentNullException. Now the goal of a guard clause is to fail fast. Interestingly if you leave it out, the next line would throw an ArgumentNullException all by itself, merely by passing it to the OrderByDescending extension method:

var sortedWords = listOfWords.OrderByDescending(word => word.Length).ToList();

I see you're using var - I like that. So sortedWords is a List<string>. I think the method could happily take any IEnumerable<string> instead of an array.

Now the next thing I see is a lie - dict would be an almost-acceptable name for any IDictionary, but it's a HashSet<T>...

var dict = new HashSet<String>(sortedWords);

And here we are. You're using System.Linq, so this loop could very well be rewritten with a much shorter Linq-expression:

foreach (var word in sortedWords)
{
    if (isMadeOfWords(word, dict))
    {
        return word;
    }
}
return null;

Turns into this one-liner (notice dict is gone!):

return sortedWords.FirstOrDefault(word => isMadeOfWords(word, sortedWords));

isMadeOfWords should be named IsMadeOfWords, and can be happy with some ICollection:

private static bool IsMadeOfWords(string word, ICollection<string> dict)
{
    if (String.IsNullOrEmpty(word)) return false;
    if (word.Length == 1)
    {
        return dict.Contains(word);
    }
    foreach (var pair in generatePairs(word).Where(pair => dict.Contains(pair.Item1)))
    {
        return dict.Contains(pair.Item2) || IsMadeOfWords(pair.Item2, dict);
    }
    return false;
}

I find that's more readable than the more concise form that ReSharper suggests:

    if (String.IsNullOrEmpty(word)) return false;
    return word.Length == 1 
        ? dict.Contains(word) 
        : generatePairs(word).Where(pair => dict.Contains(pair.Item1))
                             .Select(pair => dict.Contains(pair.Item2) || IsMadeOfWords(pair.Item2, dict))
                             .FirstOrDefault();

And then generatePairs should be renamed to GeneratePairs and can return IEnumerable<Tuple<string, string>> instead of List<Tuple<string, string>>. The only thing that itches here is the absence of var in for(int i = 1... - if you're going to use var, might as well go all the way!

I'd put that logic in its own class, and then... looks good!