6
\$\begingroup\$

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));
        }
    }
}
\$\endgroup\$
5
\$\begingroup\$

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!

\$\endgroup\$
  • \$\begingroup\$ 1. Static is OK in this case - no mutation e.g. Math.Sin 2. IEnumberable - sure, but only for public interface FindLongestWords 3. By dict I meant dictionary of words not IDictionary 4. private methods in C# should start with lower case. 5. ReSharper suggestion is ugly as hell. \$\endgroup\$ – Lukasz Madon Oct 26 '13 at 18:36
  • 1
    \$\begingroup\$ Also if you remove HashSet contains look up is O(n) not O(1) \$\endgroup\$ – Lukasz Madon Oct 26 '13 at 18:39
  • \$\begingroup\$ 1. Fine, but not in Program class 3. I think words would be appropriate and less confusing 4. That makes it look like Java code; I always capitalize method names but we can argue all night! 5. Agreed, I put it there just to show how it could be written as a return statement. And you're probably right about HashSet.Contains vs Linq IEnumerable.Contains, I can't wait to read an answer that covers performance and algorithm...and Hell should start with uppercase 'H' :) \$\endgroup\$ – Mathieu Guindon Oct 26 '13 at 20:33
  • \$\begingroup\$ The capitalization convention for methods in C# is PascalCase, according to Microsoft; here's why. \$\endgroup\$ – BCdotWEB Sep 29 '14 at 8:27
  • \$\begingroup\$ @lukas Methods in C# always are pascal cased \$\endgroup\$ – IEatBagels Sep 29 '14 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.